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