CS 598 TMC, Fall 2018

Geometric Approximation Algorithms


Instructor

Timothy Chan (Siebel 3230, tmc "at" illinois.edu, office hours: Tue 11:00-12:00 or by appointment)

Meeting Time and Place

Wed & Fri 11:00-12:15, Siebel 1103

Course Overview

This course is about approximation algorithms in computational geometry, which deals with problems involving geometric data (mostly in low dimensions). We will see how approximation allows us to solve such problems faster -- obtaining linear (or even sublinear) algorithms for many geometric problems in P, and polynomial algorithms for many NP-hard geometric problems.

We will study a variety of fundamental problems, chosen to illustrate important techniques in the area. (Occasionally, we will touch on some recent research results and open questions.) Possible topics include:

Prerequisite: Prior knowledge in computational geometry or approximation algorithms is not required, but a solid background in algorithm design and analysis (e.g., at the level of CS 374) is assumed.

Course Work

(Assignments may be done in groups of at most 2; presentations and projects are to be done individually.)

See guidelines for presentation and project.

References

There is no required textbook, but you may find the following general references useful (especially Sariel's book):

Piazza

Lectures

(I'll provide copies of my handwritten notes, and links to relevant papers, below...)

Aug 29, 31: The diameter problem

Sep 5: The diameter problem (cont'd): polynomial method

Sep 7: The width problem

Sep 12, 14, 19: eps-kernels/coresets

Sep 21, 26: Approximate range counting problems

Sep 28, Oct 3: Approximate range counting problems (cont'd): 1+eps factor

Oct 5, 10: Proximity problems: bichromatic closest pair, nearest neighbors

Oct 12: EMST, spanners