The course covers various topics in geometric optimization.

Prerequisite: Design of Algorithms 202-1-2041.
Some background in Computational Geometry is needed in order to understand the material. Most of this background will be provided in class when it becomes relevant; in some cases though the students will be refered to specific pages in one of the Computational Geometry textbooks.

Most of the material is taken from recent papers and cannot 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:

Several home assignments will be given; students will particiapte in the presentation of the material; there will be no exams; attendance is mandatory.

Syllabus:

Various topics in geometric optimization including

1. Parametric searching and related techniques
2. Clustering
3. Facility location (including guarding problems)
4. Shortest paths
5. Variants of the Euclidean TSP
6. Matching in geometric graphs
7. Power assignment problems in wireless networks

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

Lectures:

• Introduction
• Searching in sorted matrices (Frederickson and Johnson, 1984), the discrete L_\infinity 2-center problem, rectilinear p-piercing
• Parametric searching (Megiddo 1983), the slope selection problem
• Randomized halving, slope selection, distance selection
• The technique of Clarkson and Shor, the diameter of a point set in 3-space
• Orthogonal range searching
• A survey of simplex range searching (partition tree, 1/r-cutting)
• Survey of fatness definitions, properties, and applications
• The shifting strategy (Paz' presentation)
  
• Euclidean TSP, One of a set TSP, TSP with  neighborhoods
• Guarding                                                                                                                                                                    
  

  ---

Homework Assignments: