ICS 266, Spring 1998:
Computational Geometry

Instructor: David Eppstein
Office: CS 358D, phone 824-8384
Email: eppstein@ics.uci.edu
Textbook: de Berg et al., Computational Geometry Algorithms and Applications, Springer-Verlag 1997

Tentative list of topics:

• Week 1: Introduction, geometric primitives [Chap. 1]
• Week 2: Arrangements of lines and segments [Chaps. 2,8]
  Homework: exercises 2.2, 2.10, 8.2, 8.12
• Week 3: Triangulation and visibility [Chaps. 3,15]
  Homework: exercises 3.6, 3.7, 15.1, 15.7
• Week 4: Linear programming [Chap. 4]
  Homework: exercises 4.7, 4.9, 4.14, 4.15
• Week 5: Orthogonal range searching [Chaps. 5,10]
  Homework: exercises 5.5, 5.12, 10.6, 10.7
• Week 6: Point location [Chap. 6]
  Homework: exercises 6.1, 6.2, 6.4, 6.14
• Week 7: Voronoi diagrams and Delaunay triangulation [Chaps. 7,9]
  Homework: exercises 7.5, 7.7, 9.7, 9.13
• Week 8: Convex hulls [Chap. 11]
  Homework: exercises 11.1, 11.2, 11.4
• Week 9: Non-orthogonal range searching [Chap. 16]
  Homework: exercises 16.4, 16.7, 16.12, 16.13
• Week 10: Video review

Other WWW geometry resources:

• Geometry in Action, applications of computational geometry.
• U. Minn. Geometry Center computational geometry software library.
• ICS 164, undergraduate computational geometry.
• The Geometry Junkyard, geometrical fun and games.
• Syllabus from spring 1996
• Other WWW geometry resources.

David Eppstein, Dept. Information & Computer Science, UC Irvine
Last update: 26 May 2006, 16:34:46 PDT