CS 763 Computational Geometry


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.


Convexity (9 hrs)

Convex hull algorithms in two dimensions. Point-line duality. Applications. Convex polyhedra and convex hull algorithms in three dimensions.

Proximity of Points (6 hrs)

Voronoi diagrams and Delaunay triangulations. Connection to convex hulls. Applications: nearest neighbors, minimum spanning trees.

Geometric Optimization (6 hrs)

Linear programming in low dimensions. Prune-and-search and randomized search techniques.

Line Segments, Planar Subdivisions, and Polygons (9 hrs)

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.

Range Searching (6 hrs)

Orthogonal range trees. Ham-sandwich cuts and partition trees. Random sampling and epsilon-cutting.