No class information available.
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, William Steiger, William Steiger, Mario Szegedy
Credits: 3
Category: A
Prerequisites: 16:198:513 (16:198:514 is recommended)
Semesters Offered:Fall
Course Learning Goals: The aims 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.
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
* algorithmic paradigms coming from Comp. Geom.: randomized, incremental algs.; parametric search.
Course Books &/or Materials: 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 (small implementation or paper presentation).
