ICS 266, Spring 2001:
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 and Wednesdays, 2:00 - 3:20 in CS 249.

Tentative Schedule

• Week 1: Introduction, geometric primitives [Chap. 1]
• Week 2: Arrangements of lines and segments [Chaps. 2,8]
      Homework due Weds. April 18th: problems 1.1, 2.10, 2.14, 8.2.
• Week 3: Triangulation and visibility [Chaps. 3,15]
• Week 4: Linear programming [Chap. 4]
      Homework due Mon. May 7th: problems 3.2, 3.3, 3.11, 4.7, 4.14.
• Week 5: Orthogonal range searching [Chaps. 5,10]
• Week 6: Point location and Binary Space Partitions [Chaps. 6,12]
      Homework due Mon. May 21st: problems 5.10, 6.2, 6.15, 10.1, 12.10.
• Week 7: Voronoi diagrams and Delaunay triangulation [Chaps. 7,9]
• Week 8: Convex hulls [Chap. 11]
• Week 9: Non-orthogonal range searching [Chap. 16]
      Homework due Fri. June 8th: problems 7.6, 7.7, 9.8, 16.16.
• Week 10: NO CLASS MONDAY; Video review Wednesday

Other Course-Related Information

• Geometry in Action, a collection of web pointers for applications of computational geometry.
• Syllabi and homeworks from previous offerings in Spring 1998 and Spring 1996.