Matya Katz ( firstname.lastname@example.org )
Office hours: Wednesday 12:15-14:00, Deichmann building (58), room 315, Tel: (08) 6461628
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.
[BKOS] Computational Geometry: Algorithms
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.
particiapte in the presentation of the material. Several home
assignments will be given. There will be no exams.