CS 598 TMC, Fall 2018
Geometric Approximation Algorithms
Instructor
Timothy Chan
(Siebel 3230, tmc "at" illinois.edu,
office hours: Tue 11:0012:00 or by appointment)
Meeting Time and Place
Wed & Fri 11:0012: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 NPhard 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:
 Extentrelated problems: diameter, width, minimum bounding box (techniques: grids,
epsilonkernels/coresets, polytope approximation, a recent polynomial method)
 Rangecountingrelated problems (techniques: random sampling, Chernoff bounds, discrepancy, shallow cuttings)
 Proximityrelated problems: closest pair, nearest neighbors, Euclidean spanners,
Euclidean minimum spanning trees
(techniques: grids, quadtrees, shifting, wellseparated pair decomposition)
 NPhard problems: geometric independent set, set cover, hitting set
(techniques: shifted grids/quadtrees,
planargraph separators and geometric separators, local search, LP rounding, union complexity, (<=k)levels, epsilonnets, quasisampling, multiplicative weights update, APXhardness)
 Other assorted problems: Euclidean traveling salesman,
clustering (kcenter/kmedian), embedding, shortest paths in unit disk graphs,
highdimensional minimum enclosing ball, ...
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
 3 or 4 assignments (problem sets), worth 40%
 Homework 1 (due Sep 28, Fri) [note (9/14): have changed Q3 to make it less trivial]
 Homework 2 (due Oct 17, Wed) [note: in Q1, all squares are axisaligned]
 Homework 3 (due Nov 9, Fri)
 Homework 4 (due Dec 5, Wed)
 presentation, worth 20%
 a project (reading some papers and writing a report,
or implementing some algorithms,
or doing some original research), worth 40%
(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):

[HP] S. HarPeled,
Geometric Approximation Algorithms,
AMS, 2011

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,
Computational
Geometry: Algorithms and Applications (3rd ed.),
SpringerVerlag, 2008

[GRT] J. Goodman, J. O'Rourke, and C. D. Toth (eds.),
Handbook of Discrete and Computational Geometry (3rd ed.),
CRC Press, 2017
Lectures
(I'll provide copies of my handwritten notes, and links to relevant papers, below...)
Aug 29, 31: The diameter problem
 Constantapprox. algorithms: factor 2 and factor sqrt{3}
 (1+eps)approx. algorithms in fixed dimensions:
1. rounding points to a grid (O(n + 1/eps^{2(d1)}) time), 2. rounding directions
(O(n/eps^{(d1)/2})), 3. combination (O(n + 1/eps^{3(d1)/2})),
4. recursion in dimension (O(n+1/eps^{d(1/2)}))
 Refs: my notes,
my paper (2002)
[Sec 2, Algorithms 14]
Sep 5: The diameter problem (cont'd)
Sep 7: The width problem
 First (1+eps)approx algorithm: rounding directions +
linear programming (O(n/eps^{(d1)/2}) time)
 Second algorithm: epsilonkernels/coresets...
 Refs: my notes,
my paper (2002)
[Sec 3, Algorithm 1]
Sep 12, 14, 19: epsilonkernels/coresets
 Algorithms: 1. fattening + rounding points (O(1/eps^{d1}) size),
2. fattening + rounding directions (O(1/eps^{d1}) size), 3. Dudley's technique (O(1/eps^{(d1)/2}) size)
 Applications to min enclosing ball/cylinder/box/..., minwidth enclosing annulus (by
linearization), sketching/streaming, outliers
 Refs: my notes (part 1 and part 2), Agarwal, HarPeled, and Varadarajan's
paper (2004)
and survey,
my paper (2006) [Sec 2]
Sep 21, 26: Approximate range counting problems
 "epsilonapproximations" (with additive error eps*n): random sampling + Chernoff (O((1/eps^2) log (1/eps)) size),
improved bounds for balls/halfspaces via discrepancy + matching with
low crossing numbers ((O~(1/eps^{22/(d+1)}) size)
 Deterministic construction of epsilonapproximations: Matousek's O(n)time algorithm for constant eps via mergeandreduce
 Refs: my notes, books on discrepancy theory by Matousek and
Chazelle
Sep 28, Oct 3: Approximate range counting problems (cont'd): 1+eps factor
Oct 5, 10: Proximity problems: bichromatic closest pair, nearest neighbors

fixed radius: grid methods (O((1/eps^d)n) time naively, or O((1/eps^{d/4})n) by epskernelrelated techniques)

arbitrary radius: compressed quadtrees, balanced quadtrees, shifting (O(n) space and
O(log U + 1/eps^d) or O((1/eps^d) log n) query time)

Refs: my notes, Sariel's book [Ch2],
my paper (1998) [Sec 3]
Oct 12, 17: Euclidean min spanning trees, spanners
Oct 19, 24: Geometric independent set, hitting set, set cover

Technique 0: greedy (O(1) approximation for independent set and piercing for arbitrary fat objects)

Technique 1: shifted grid (PTAS for (weighted) independent set and piercing for
fat objects of similar sizes)

Technique 2: shifted quadtree (PTAS for (weighted) independent set and piercing for
arbitrary fat objects)

Technique 3: geometric separators, via
Smith and Wormald's theorem (PTAS for independent set and piercing for
arbitrary fat objects)

Refs: my notes,
Hochbaum and Maass's original paper (1985), my paper (2001)
Oct 26: Geometric independent set, hitting set, set cover (cont'd)
Oct 31, Nov 2: Geometric independent set (cont'd)

LP rounding + (<=k)level (O(1) approximation for independent set for (weighted) objects with low union complexity)

randomized LP rounding (O(log n/loglog n) approximation for independent set for (weighted) 2D rectangles)

Refs: my notes,
my paper with Sariel (SoCG'09)
Nov 7, 9: Geometric set cover (cont'd)

LP rounding + epsilonnets (O(1) approximation for set cover for objects with low union complexity), or multiplicative weights update + epsilonnets

LP rounding + weighted epsilonnets via "quasisampling" (O(1) approximation for set cover for weighted objects with low union complexity)

Refs: my notes (unweighted and weighted),
Bronnimann and Goodrich's paper,
Varadarajan's and CGKS's quasisampling papers
Nov 14, 16: Geometric independent set (cont'd)
 Fox and Pach's separator approach (n^eps approximation for independent set of line segments or curves)
 Adamaszek and Wiese's separator approach (QPTAS for independent set of line segments or curves)
 APXhardness (for independent set for 3D boxes, and set cover for fat triangles and fat rectangles)

Refs: my notes,
papers by Fox and Pach, Adamaszek, HarPeled, and Wiese,
HarPeled, and Grant and me
Nov 28: Euclidean traveling salesman
Nov 30, Dec 5: Min enclosing ball in high dimensions
 Badoiu, HarPeled, and Indyk's algorithm, as analyzed by Badoiu
and Clarkson (coreset of size O(1/eps), without dependencies on d)
 another iterative algorithm by Badoiu and Clarkson (in O((1/eps)^2 dn) time)
 1pass streaming algorithms (factor 3/2 by ZarrabiZadeh and C., and
factor sqrt{2} by Agarwal and Sharathkumar)
 Refs: my notes,
Badoiu and Clarkson (2003),
ZarrabiZadeh and C. (2006),
Agarwal and Sharathkumar (2010),
C. and Pathak (2013)
Dec 7, 12: Student presentations