Skip to content Skip to navigation

16:198:529 - Computational Geometry

Computational geometry addresses geometric questions using ideas from algorithms, data structures, complexity theory, and combinatorics. As such, it provides a nice set of applications from these disciplines and also contains features that are interesting and useful in their own right. The aim of this course is to provide the student with a solid foundation in the field.


16:198:513 OR 16:198:512 (16:198:514 is recommended)


    *  Geometric objects and data structures
    * Convex hulls in the plane and higher dimensions
    * Lower bound proofs
    * Arrangements of lines, plane sweep, duality
    * Decomposition and partitioning
    * Searching and planar point location
    * Voronoi diagrams and Delaunay Triangulations
    * Farthest-pair and closest-pair problems
    * Geometric Optimization and Linear Programming
    * algorithmic paradigms coming from Comp. Geom.: randomized, incremental algs.; parametric search.

Course Material: 

Suggested Text: "Computational Geometry: Algorithms and Applications", Third Ed., Mark de Berg, Mark van Kreveld, Mark Overmars, Ottfried Schwartzkopf, Springer, New York, 2008.

Expected Work: 

Weekly reading, a problem set, an examination, a project (paper presentation; on rare occasion, implementation projects were allowed).

The usual practice is a take-home exam.
Learning Goals: 

The aim of this course is to provide the student with a solid foundation in the field, and to show some of the many applications of Computational Geometry.

William Steiger
Course Type: 
Course Name: 
Computational Geometry