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.
* 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.
Suggested Text: "Computational Geometry: Algorithms and Applications", Third Ed., Mark de Berg, Mark van Kreveld, Mark Overmars, Ottfried Schwartzkopf, Springer, New York, 2008.
Weekly reading, a problem set, an examination, a project (paper presentation; on rare occasion, implementation projects were allowed).
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.