Description
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.
William Steiger, Mario Szegedy
Credits: 3
Category: A
Prerequisites: 16:198:513 (16:198:514 is recommended)
Semesters Offered:Fall
Topics: * 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
* The randomized, incremental paradigm, parametric search.
Expected Work: Weekly reading, a problem set, an examination, a project (small implementation or paper presentation).
