Prof. Matya Katz
 Spring 2003

The course covers various topics in geometric optimization.

Prerequisite: Computational Geometry 202-2-5121

Most of the material is taken from recent papers and cannot (yet) be found in textbooks.
There are several survey papers on geometric optimization and on specific topics in geometric optimization including
the surveys by  Agarwal and Sharir  on geometric optimization and by  Agarwal and Sen on randomized techniques for geometric optimization.

A good textbook in computational geometry is

• De Berg, van Kreveld, Overmars and Schwarzkopf,
  Computational Geometry, Algorithms and Applications (1997); second edition (2000) 
  

Course requirements: 

Syllabus:

Various topics in geometric optimization including

1. Parametric searching
2. Clustering
3. Facility location
3. Computing the diameter in 3 dimensions
4. Shortest paths
5. Euclidean TSP
6. Matching in geometric graph

We will present both exact and approximate solutions for the problems above, emphasizing some of the general techniques that are used.