Fall 2019

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: Wednesday 14:15-16:00, Alon
building (37), room 212, Tel: (08) 6461628

**Teaching Assistant:**

Elad Sulami

**Class Time:**

Monday 14-16 (building 97, room 202)

**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

- Computational Geometry: Algorithms and
Applications, 3
^{rd}edition, 2008

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%).

Assignment No. 1 –
due November 18, 2019

Assignment No. 2 –
due December 4, 2019

Assignment No. 3 –
due December 23, 2019

Assignment No. 4 –
due January 20, 2020

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.

Introduction, parametric searching (slope selection), randomized halving,
searching in sorted martices and applications,
Clarkson-Shor (the diameter of a set of points in ),
geometric local search (a PTAS for hitting a set of disks by points from *P* ), min dom set via
local search for terrain-like graphs and for disk graphs (presented by Stav and Amit & Itamar), Welzl’s smallest enclosing disk algoritm (presented by Katya & Tamar), TSP – Christofides’ algorithm (presented by Omri & Ron), Arora’s algorithm (presented by
Michael & Shaked).

**Last
update: January 8, 2020**