Prerequisite:
Algorithms
Some background in
Computational Geometry is needed in order to understand some of the material.
Most of this background will be provided in class when it becomes relevant; in
some cases though the students will be referred to specific pages in one of the
Computational Geometry textbooks.
Announcements:
Instructor:
Matya Katz ( matya@cs.bgu.ac.il )
Office hours: Monday 12:15-13:00 (and by
appointment) Office hourse
Teaching Assistant:
Class Time:
Tuesday 16-18
Course Description:
The course deals with various topics in
geometric optimization. Several techniques and a selection of approximation
algorithms will be presented. More precisely, a subset of the following
optimization techniques will be discussed: parametric searching and searching
in sorted matrices, the shifting strategy, geometric local search, epsilon-nets
and epsilon-approximations, core sets, (geometric) linear programming. In
addition, approximation algorithms (mostly based on these techniques) dealing
with, e.g., geometric covering, (wireless) network design, and facility
location will be presented.
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.
References will be provided later on.
A recommended
textbook in computational geometry is
M. de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
Springer-Verlag
The final grade will be determined by 4
homework assignments (~50%), and a final project which may include (among other
requirements) the presentation of a scientific paper (~50%).
Below you will find, after each class, a
brief summary of the topics covered in class. This should not be taken as a
complete description of the course's content.
Last
update: October 14, 2020