Recommended:
| Texts | Important Dates | Assignments | Syllabus | Lectures | Grading | Links |
Instructor: Dianna Xu , 246A Park Hall, 526-6502
E-Mail: dxu at cs dot brynmawr dot edu
WWW: http://cs.brynmawr.edu/~dxu
Lecture Hours: Tuesdays & Thursays,
11:15am - 12:45pm
Room: Park 349
Office hour: Tuesdays 2-4pm and by appointment
Lab
| Lab Policy: | Labs and lectures will often be exchangable in this course, depending on how the course and projects progress. |
|---|---|
| Lab Hours: | TBA |
| Lab Room: | Park 231 or 232 |
| Availability: | The labs are open 24 hours a day, seven days a week.There are times that 231 is reserved for other classes. |
| Textbooks: |
| Discrete and Computational Geometry by Devadoss Satyan and Joseph O'Rourke, 2011.Princeton University Press. ISBN 978-0691145532. |
|---|---|---|
|
| Computational Geometry: Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, 2008. Springer, 3rd Edition. ISBN 978-3540779735. | |
Recommended:
|
| Computational Geometry in C by Joe O'Rouke, 2nd Edition. Cambridge University Press. ISBN 978-0521649766 |
| Software | We will be using a variety of programming languages and tools. |
January 22 : First lecture
May 2: Last lecture
Midterm: 4/16/13
Project: Last day of exam period
| Week | Topic |
|---|---|
| 1 | Course overview, art galleries and polygon triangulation |
| 2 | Dissections |
| 3 | class cancelled, I am out of town |
| 4 | trapezoidalization, Monotone partitioning, Area and segment intersection |
| 5 | Convex hull algorithms |
| 6 | Triangulations |
| 7 | Delaunay and other special triangulations |
| 8 | Spring break |
| 9 | Voronoi Diagrams |
| 10 | Curves: medial axis, skeleton and Minkowski sums |
| 11 | Curve shortening, geometric flow, Poincaré conjecture |
| 12 | Polyhedra |
| 13 | Exam |
| 14 | Project presentations |
| 15 | Motion planning, wrap up |
For all graded work that receive numerical scores, guidelines of letter grades corresponding to lab/exam score levels will be given during the semester. At the end of the semester, a total score (to which the corresponding final grade is assigned) will be calculated from a weighted average of all scores according to the following weights:
| Class participation | 10% | |
| Assignments | 40% | |
| Midterm | 25% | |
| Final project | 25% | |
| Total: | 100% |
There will be weekly to bi-weekly assignments for this course, involving both theory (mathematics or algorithm design) and implementations (any programming language of choice). The topics are sufficiently new that there are many open and unsolved problems. We will explore serveral, both in class and in assignments/projects. Students are encouraged to collaborate on all assignments, except for the final project. The definition of collaboration differs depending on whether the assignment is theory or implementation. On theory, collaboration means discussion but individual write-ups of solutions. If collaborating on programming exercises, only one copy of code needs to be handed in. The final project includes a brief, preliminary in-class presentation. More details will be given as the semester progresses.