Advanced Topics in CS (202-2-5521)

Geometric Optimization
Spring 2005

Prerequisite: Algorithms



Matya Katz  (

Office hours: Wednesday 12:15-14:00, Deichmann building (58), room 315, Tel: (08) 6461628


Class Time:

Monday 14-16

Course Description:

The course deals with various topics in geometric optimization. Several optimization techniques and a selection of optimization algorithms will be presented. Among the techniques, we mention the parametric search technique of Megiddo and the technique of Frederickson and Johnson. Among the optimization problems we mention optimal facility location problems, maximal containment problems, optimal path problems, etc.


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.

Below is a list of several textbooks that contain some necessary background.

[BKOS] Computational Geometry: Algorithms and Applications (2nd edition),
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2000.

[E] Algorithms in Combinatorial Geometry, H. Edelsbrunner, Springer-Verlag, 1987.

[M] Computational Geometry: An Introduction Through Randomized Algorithms, K. Mulmuley, Prentice Hall, 1994.

[O] Computational Geometry in C (2nd edition), J. O'Rourke, Cambridge University Press, 1998.

[PS] Computational Geometry: An Introduction (2nd edition), F. Preparata and M. Shamos, Springer-Verlag, 1988.

Assignments, Exam and Grades:

Students will particiapte in the presentation of the material. Several home assignments will be given. There will be no exams.

Last update January 17, 2005.