Discussion - 1.0 hours
Summary of Course Content
I. Introduction: polygon trapezoidation
II. Geometry of convex hull, Voronoi diagram and Delaunay triangulation
III. Algorithms for their construction
IV. Arrangements of curves, surfaces and lines
V. Theory of oct-trees, kd-trees and BSP trees
VII. 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.
Potential Course Overlap
There is no significant overlap with other courses.