Home Bookmarks Papers Blog

598: Approximation Algorithms in Geometry

Fall 2004


Lecture notes

A more updated version of the lecture notes is available here.
Tue/Thu 16:15 PM - 17:30
SC 1214.

Mailing list

Please register.
In this course, we would cover techniques used in developing efficient approximation algorithms in computational geometry and related fields. Topics covered (would hopefully) include:
    1. Random sampling: epsilon-net and approximations.
    2. Discrepancy.
    3. Embeddings, dimension reduction, JL lemma, Bourgain's embeddings.
    4. Convex shape approximation - John theorem and Dudley theorem.
    5. Coresets.
    6. Shape fitting in low dimensions (with or without outliers).
    7. Fast clustering in low dimensions: k-center, k-median and k-means.
    8. High dimensional shape fitting.
    9. Approximate nearest neighbor in low and high dimensions.
    10. Curve simplification, Frechet distance, and morphing width.
    11. Approximating the diameter in low-dim.
    12. Approximating the Euclidean TSP.
    13. What is dimension? Linear classification and margin.
    14. Streaming.
Emphasize would be put on open problems, and research oriented activities.
Last modified: Mon Mar 27 13:57:56 CST 2006