# Advanced
Topics in CS (202-2-5521)

# Geometric
Optimization

Spring
2005

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.

### Bibliography:

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.