Lecture: 3 hours

Prerequisite: Courses 175, 222A

Grading: Letter; homework (30%), project (50%), presentation (20%)

Catalog Description:
Mathematics of unstructured data. Algorithms for data structures such as Voronoi diagrams, oct-trees, and arrangements. Applications in computer graphics, concentrating on problems in three-dimensions. Offered in alternate years.

Provide enough background to allow students to use current results or software from computational geometry in their work or to begin pursuing research in the area.

Expanded Course Description:

  1. Introduction: polygon trapezoidation
  2. Geometry of convex hull, Voronoi diagram and Delaunay triangulation
  3. Algorithms for their construction
  4. Arrangements of curves, surfaces and lines
  5. Theory of oct-trees, kd-trees and BSP trees
  6. Applications
  7. Special topics

Projects will be agreed upon with the instructor early in the quarter. Typically a project will be a survey of a few current research papers, but programming or original theory projects are also possible.

M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 2000. This will be supplemented by recent research papers.

Instructors: N. Amenta and N. Max

Prepared by: N. Amenta (March 2004)

Overlap Statement:
There is no significant overlap with other courses.

Revised: 12/92