ICS 164, Winter 2007:
Computational Geometry
General Course Information
Coursework will consist of weekly homeworks, a midterm, and a
comprehensive final exam. The course text will be Computational
Geometry Algorithms and Applications, 2nd ed., by de Berg, van Kreveld,
Overmars, and Schwarzkopf (Springer-Verlag, 2000). The course meets
Mondays, Wednesdays, and Fridays, 2:00 - 2:50 in ICF 101.
Homeworks will be assigned on Fridays, due in the ICS distribution center the following Friday.
Tentative Schedule
- Week 1: Introduction and geometric primitives [Chap. 1].
NO LECTURE MONDAY JANUARY 8.
Homework: Problems 1.6, 1.9
- Week 2: Projective geometry [Sec. 8.2].
ACADEMIC HOLIDAY MONDAY JANUARY 15.
Homework: Problems 8.2, 8.6, 8.8
- Week 3: Arrangements of lines and segments [Chaps. 2,8].
Homework: Problems 2.2, 2.5, 8.14
- Week 4: Triangulation and visibility [Chaps. 3,15]
Homework: Problems 3.3, 3.6, 15.1
- Week 5: Linear programming [Chap. 4].
MIDTERM FRIDAY FEBRUARY 9.
- Week 6: Orthogonal range searching [Chaps. 5,10,14]
Homework: Problems 5.9, 10.6(parts b and c only), 14.7, 14.12
ACADEMIC HOLIDAY MONDAY FEBRUARY 19.
- Week 7: Point location, binary space partitions [Chaps 6,12].
Homework: Problems 6.1, 6.14, 12.3
- Week 8: Voronoi diagrams and Delaunay Triangulations [Chaps. 7,9].
Homework: Problems 7.1, 7.5, 9.11
- Week 9: Convex hulls [Chap. 11]
Homework: Problems 11.1, 11.4, 11.7
- Week 10: Non-orthogonal range searching [Chap. 16]
Other Course-Related Information