CS 598 TMC, Fall 2018

Geometric Approximation Algorithms


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.


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



(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)

Sep 7: The width problem

Sep 12, 14, 19: epsilon-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, 17: Euclidean min spanning trees, spanners

Oct 19, 24: Geometric independent set, hitting set, set cover

Oct 26: Geometric independent set, hitting set, set cover (cont'd)

Oct 31, Nov 2: Geometric independent set (cont'd)

Nov 7, 9: Geometric set cover (cont'd)

Nov 14, 16: Geometric independent set (cont'd)

Nov 28: Euclidean traveling salesman

Nov 30, Dec 5: Min enclosing ball in high dimensions

Dec 7, 12: Student presentations