Prof. Micha Sharir  (michas@tau.ac.il)
                                                   Fall 2009, Monday 16:00-19:00, Shenkar (Physics) 105

Assignments:

Assignment 1, due November 9, 2009
Assignment 2, due November 23, 2009
Assignment 3, due December 21, 2009
Assignment 4, due January 4, 2010
Assignment 5, due January 25, 2010

The class on January 11, 2010 is CANCELLED
There will be a make-up class on January 25, 2010, 16:00--19:00

Final Exam: An in-class exam, on February 4, 2010, 9:00--12:00.
The exam will be with open material (of any kind).
There will be a choice: Four out of five questions.
The questions will be much more modest than the exercises.

BEHATZLAKHA!!

The course covers various topics in geometric optimization.
The course Computational Geometry is a prerequisite.
Otherwise, by special permission of the teacher.

There is no textbook that covers the material given in the course.
There are several survey papers and other written material that will be distributed during the class.

Survey Papers:

S. Toledo's M.Sc. Thesis . Chapter 1 is a good source on parametric searching and related techniques.
Agarwal-Sharir's survey on geometric optimization .
Agarwal-Sen's survey on randomized techniques for geometric optimization .
Chan's randomized technique .
Gaertner-Welzl's survey on randomized techniques for linear programming and related problems .
Slides by Agarwal on clustering .
Arora's survey on TSP approximation.
Survey on coresets.

Other Course Material:

A note on Megiddo's 3-dimensional LP algorithm.
The subexponential LP paper by Matousek, Sharir, Welzl.
Agarwal-Procuppiuc' p-center algorithm.
Rectlinear center paper.
2-Center paper.
Overmars - van Leeuwen paper.
Chan's approximation algorithms.
Paper on width, smallest annulus, etc.

A reminder of the textbooks in computational geometry:

• De Berg, van Kreveld, Overmars and Schwarzkopf,
  Computational Geometry, Algorithms and Applications (1997); second edition (2000)
  (the most recent and best textbook)
• Preparata and Shamos, 
  Computational Geometry, An Introduction (1985)
  (the first textbook on the subject, somewhat outdated)
• Edelsbrunner, 
  Algorithms in Combinatorial Geometry (1987)
  (another old and slightly more advanced textbook)
• Mehlhorn, 
  Data Structures and Algorithms, 3: Multidimensional Searching and Computational Geometry (1983)
  (oldest book, not easy to read)
• Mulmuley, 
  Computational Geometry: An Introduction Through Randomized Algorithms} (1993)
  (uses very special approach)
• O'Rourke, 
  Computational Geometry in C (1994)
  (elementary, practically oriented; has lots of code)
• Boissonnat and Yvinec, 
  Algorithmic Geometry (1998)
  (another `modern' textbook)

Course requirements: Final exam and a few (four--five) assignments during the semester.
Assignments will be graded and will comprise part (about 20 percent) of the final grade.

The syllabus of the course

The syllabus may not exactly coincide with the material that will be taught. It will be (slightly) updated during the semester

(1) Parametric Searching:

• The basic technique
• Illustration: Slope selection
• Issues in parallel computation
• Cole's improvement
• Alternatives: Probabilistic approach, Expanders, Monotone Matrix Searching, Chan's technique

(2) Linear Programming: Geometric Approach:

• Review of Megiddo's algorithm and Seidel's randomized algorithm. Algorithms by Clarkson and by Matousek et al.
• Abstract linear programming: Framework, geometric applications, variants

(3) Search in Monotone Matrices:

(4) Facility Location:

• The p-center probolem
• Efficient algorithm for the 2-center problem
• Exact and approximate algorithms for the general case
• Clustering
• The p-median problem and other variants

(5) Diameter in Three Dimensions:

• A randomized algorithm
• A deterministic algorithm

(6) Geometric Optimization and Arrangements:

• Hausdorff distances
• Width in three dimensions
• Polygon placements; biggest stick in a polygon.

(7) Shortest Paths:

• Shortest paths in the plane
• Shortest paths on a convex polytope and in polyhedral 3-D regions
• Approximate shortest paths

(8) Approximation Algorithms for Geometric Optimization:

• Euclidean travelling salesperson
• Approximating diameter, width, minimum-width annuli and cylinders

(9) Approximate Nearest Neighbor Search in Higher Dimensions:

• Review of recent techniques