Seminar on Geometric Approximation Algorithms, spring 11/12

Haim Kaplan

We will cover part of the book on Geometric Approximation Algorithms by Sariel Har Peled (AMS 2011).

Tentative schedule

Chapter 1. The power of grids – Closest Pair and Smallest Enclosing Disk

Chapter 2. Quadtrees – Hierarchical Grids,  Tamar Lavee

Chapter 3. Well Separated Pair Decomposition, Eyal Altshuler

Chapter 4. Clustering, Ariel Persico

Chapter 5. On Complexity, Sampling, and epsilon-nets, and eplison-samples, Yuval Snappir

Chapter 6. Approximation via Reweighting, Eran Kravitz

     Chapter 7. Yet Even More on Sampling (skip)


     Chapter 8. Sampling and the moment technique, Dima Blokh


     Chapter 9. Depth Estimation via Sampling, Eliad Zfadia


     Chapter 10. Approximating the Depth via Sampling and Emptiness, Adi Vardi


     Chapter 11. Random Partition via Shifting, Tomer Margalit


     Chapter 12. Good triangulations and meshing, Ofer Rothschild


You can find the full table of contents and some early version of the book here. But please use the most recent version for preparing your presentation.