598: Approximation Algorithms in Geometry
Fall 2004
Lecture notes
A more updated version of the lecture notes is available here .
Random sampling: epsilon-net and approximations.
Discrepancy.
Embeddings, dimension reduction, JL lemma, Bourgain's
embeddings.
Convex shape approximation - John theorem and Dudley theorem.
Coresets.
Shape fitting in low dimensions (with or without outliers).
Fast clustering in low dimensions: k-center, k-median and
k-means.
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.
Streaming.
Emphasize would be put on open problems, and research oriented
activities.