Prerequisite: Algorithms
Announcements:
Instructor:
Matya
Katz (
matya@cs.bgu.ac.il )
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.
Students will
particiapte in the presentation of the material. Several home
assignments will be given. There will be no exams.