Prof. Micha Sharir  (michas@tau.ac.il)
                                                   Fall 2013, Tuesday 15:00-18:00, Kaplun 324

*** Returned assignments are in Schreiber 114 (including Ex. 4) ***

*** Brief solution to assignment 4 is also available now ***

Solution to assignment 4

*** Brief solutions to assignments 1--3 are now available ***

Solution to assignment 1
Solution to assignment 2
Solution to assignment 3

*** Assignment 5 is now available ***

*** Assignment 4, Problem 1(b), has been modified ***

Assignments:

Assignment 1, due November 12, 2013
Assignment 2, due December 3, 2013
Assignment 3, due December 24, 2013
Assignment 4, due January 14, 2014
Assignment 5, due before the exam, in my mailbox, or electronically

Final Exam: An in-class exam, Sunday, 9.2.14, 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!!

Scanned lecture notes (courtesy of Igor Tubis)
(These notes are not edited. They are given as a service to the students, who should use them accordingly.)

Lecture 1, 15.10.13, scanned notes

Lecture 2, 22.10.13, scanned notes

Lecture 3, 29.10.13, scanned notes

Lecture 4, 5.11.13, scanned notes

Lecture 5, 12.11.13, scanned notes

Lecture 6, 19.11.13, scanned notes

Lecture 7, 26.11.13, scanned notes

Lecture 8, 3.12.13, scanned notes

Lecture 9, 10.12.13, scanned notes

Lecture 10, 17.12.13, scanned notes

Lecture 11, 24.12.13, scanned notes

Lecture 12, 31.12.13, scanned notes

Lecture 13, 7.1.14, scanned notes

Lecture 14, 14.1.14, scanned notes

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