To provide the student with an introduction to the design, analysis, and application
of algorithms for geometric problems. Students are expected to have basic knowledge
of algorithm design and analysis.
Computational Geometry: Algorithms and Applications, by de Berg, van Kreveld,
Overmars, and Schwarzkopf, Springer-Verlag, 1997.
Three hours of lecture per week.
Convex hull algorithms in two dimensions. Point-line duality. Applications. Convex polyhedra and convex hull algorithms in three dimensions.
Voronoi diagrams and Delaunay triangulations. Connection to convex hulls. Applications: nearest neighbors, minimum spanning trees.
Linear programming in low dimensions. Prune-and-search and randomized search techniques.
Intersection and arrangement of line segments. Plane-sweep and randomized incremental algorithms. Segment trees. Point location data structures. Triangulation of simple polygons. Other problems for polygons: decomposition, visibility, motion planning.
Orthogonal range trees. Ham-sandwich cuts and partition trees. Random sampling and epsilon-cutting.