598: Approximation Algorithms in Geometry
A more updated version of the lecture notes is available here.
Tue/Thu 16:15 PM - 17:30
In this course, we would cover techniques used in developing efficient
approximation algorithms in computational geometry and related fields.
Topics covered (would hopefully) include:
Emphasize would be put on open problems, and research oriented
- Random sampling: epsilon-net and approximations.
- Embeddings, dimension reduction, JL lemma, Bourgain's
- Convex shape approximation - John theorem and Dudley theorem.
- Shape fitting in low dimensions (with or without outliers).
- Fast clustering in low dimensions: k-center, k-median and
- High dimensional shape fitting.
- Approximate nearest neighbor in low and high dimensions.
- Curve simplification, Frechet distance, and morphing width.
- Approximating the diameter in low-dim.
- Approximating the Euclidean TSP.
- What is dimension? Linear
classification and margin.
Last modified: Mon Mar 27 13:57:56 CST 2006