Bryn Mawr College
CS 380: Recent Advance in Computer Science-- Computational Geometry
Fall 2009
Course Materials
General Information
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: Mondays & Wednesdays,
2:30pm to 4:00 pm
Room: Park 232
Office hour: M/W 4-5pm 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: |
PC Lab Room 231 (Science Building) 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.
|
|---|
Texts & Software
| Textbooks: | 
| Computational Geometry: Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars,
2008. Springer, 3rd Edition. ISBN 978-3540779735.
|
|
| 
| 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. The labs/projects will use the
Linux OS.
|
Important Dates
August 31 : First lecture
December 9: Last lecture
Project: Last day of exam
Assignments
- A1 (due Wed 9/9 in class)
- A2 (due Wed 9/16 in class)
- A3 (due Mon 9/28 in class)
- A4 (due Wed 10/7 in class)
- A5 (due Wed 10/28 in class)
- A6 (due Mon 11/09 in class)
- A7(due Wed 11/17 in class)
- Final Project (due Fri 12/18)
Planned Syllabus
| Week
| Topic |
|---|
| 1 |
Course overview, triangulation |
| 2 |
Triangulation |
| 3 |
Area and segment intersection, trapezoidalization, Monotone Mountains |
| 4 |
Convex hull in 2D |
| 5 |
Graham scan, more convex hull |
| 6 |
Convex hull in 3D |
| 7 |
Fall Break! |
| 8 |
Voronoi Diagrams |
| 9 |
Delaunay Triangulation |
| 10 |
Arrangements |
| 11 |
Search and intersection |
| 12 |
Binary space partitions |
| 13 |
Motion planning |
| 14 |
Quadtrees |
| 15 |
Project presentations, wrap up |
Lectures
- Week 1
Aug 31: Introduction and general discussion of computational geometry and related topics.
Read: de Berg Chapter 1.
Sep 2: The art gallery theorems. Triangulation.
Read: O'Rourke Chapter 1, p 1-24. de Berg 3.1. Art Gallery applet
Assignment: A1 (due Wed 9/9 in class)
- Week 2
Sep 7: Labor day
Sep 9: Area of polygon. Triangulation, implementation
Read: O'Rourke Chapter 1, p 16-43.
Assignment: A2 (due Wed 9/16 in class)
- Week 3
Sep 14: Trapezoidalization. Monotone polygons.
Read: O'Rourke Chapter 2, p 44-51. de Berg 3.2.
Sep 16: Triangulating monotone polygons. Monotone Mountains. Randomized algorithms.
Read: O'Rourke Chapter 2, p 51-62.
de Berg 3.3 and 3.4
Assignment: A3 (due Mon 9/28 in class)
- Week 4
Sep 21: Map overlays, line segment intersection, doubly-connected edge list.
Read: de Berg Chapter 2. O'Rourke Chapter 7, sections 7.1 and 7.2
Sep 23: 2D convex hull.
Read: O'Rourke Chapter 3, p 63-72
- Week 5
Sep 28: 2D convex hull, continued.
Read: O'Rourke Chapter 3, p 69-86
Assignment: A4 (due Wed 10/7 in class)
Sep 30 : Lecture cancelled, I am out of town.
- Week 6
Oct 5: Graham scan implementation, lowerbound, incremental and divide and conquer.
Read: O'Rourke Chapter 3, p 77-95
Oct 7: Polyhedra, Platonic solids, Euler's formula, convex hull in 3d.
Read: O'Rourke Chapter 4,
p101-109, de Berg 11.1 and 11.2. Polytopes!
Assignment: A5 (due Wed 10/28 in class)
- Week 8
Oct 19: hw3 and hw4, Platnic Solids, Euler's formula.
Read: O'Rourke Chapter 4, p 101-109
Oct 21: Euler's formula, convex hull in 3d.
Read: O'Rourke Chapter 4, p106-117, de Berg 11.1 and 11.2.
- Week 9
Oct 26: Voronoi diagrams and Delaunay triangulation, introduction.
Read: O'Rourke Chapter 5, p 155-164, de Berg 7.1
Oct 28: Computation of Voronoi diagrams. Applications. Voronoi applet, Voroglide, fortune's algorithm
Read: O'Rourke Chapter 5, p165-181
Assignment:A6(due Mon 11/09 in class)
- Week 10
Nov 2: Voronoi diagrams applications continued: Medial Axis. Delaunay Triangulation applications: Minimum Spanning Tree
Read: O'Rourke Chapter 5, p 165-181
Nov 4: Triangulation of a point set, the flip graph, legal triangulation and Delaunay Triangulation
Read: O'Rourke Chapter 5, p165-181, de Berg 7.2
- Week 11
Nov 9: Legal edges and Thales' theorem. Randomized incremental construction of Delaunay Triangulation.
Read: de Berg 9.2, 9.3, 9.4
Assignment:A7(due Wed 11/17 in class)
Nov 11: Convex hull and Delaunay triangulation in higher dimensions. Final Project.
Read: O'Rourke Chapter 5, p182-191. de Berg 11.5
Assignment: Final Project (due Fri 12/18)
- Week 12
Nov 16: Arrangements
Read: O'Rourke Chapter 6, de Berg Chapter 8
Nov 18: Motion planning, Minkowski sums, curve shortening
Read: O'Rourke Chapter 8, de Berg Chapter 13
Grading
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:
|
| Assignments
| 50%
|
|
| 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.
Links