ICS 266, Spring 2003:
Computational Geometry

General Course Information

Coursework will consist of biweekly homeworks and a comprehensive final exam. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. 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 CS 253.

Tentative Schedule

• Week 1: Introduction, geometric primitives, projective geometry [Chap. 1]
• Week 2: Special seminar in CS 432, April 7: Adam Buchsbaum
  Arrangements of lines and segments [Chaps. 2,8]
  Homework due Friday, April 18: problems 2.2, 2.5, 8.2, 8.14
• Week 3: Triangulation and visibility [Chaps. 3,15]
• Week 4: Special seminar in CS 432, April 21: Lars Arge
  Linear programming [Chap. 4]
  Homework due Friday, May 2: problems 3.6, 4.7, 4.12, 15.1
• Week 5: Orthogonal range searching [Chaps. 5,10]
• Week 6: Point location, binary space partitions [Chaps 6,12]
• Week 7: Voronoi diagrams [Chap. 7]; no class Weds-Fri May 14-16
  Homework due Friday, May 23: problems 5.11, 6.7, 7.7, 10.9, 12.10
• Week 8: No class Mon-Weds May 19-21; Delaunay triangulation [Chap. 9]
• Week 9: Convex hulls [Chap. 11]
  Homework due Friday, June 6: problems 9.8, 9.17, 11.2.
  Hint for 9.17: you should only need four vertices in your counterexample.
• Week 10: Non-orthogonal range searching [Chap. 16]

Other Course-Related Information

• Sample final exam.
• Homework and sample final solutions.
• Geometry in Action, a collection of web pointers for applications of computational geometry.
• Syllabi and homeworks from previous offerings in Spring 2001, Spring 1998, and Spring 1996.