AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

Geometric Approximation Algorithms

About this Title

Sariel Har-Peled, University of Illinois at Urbana-Champaign, Urbana, IL

Publication: Mathematical Surveys and Monographs
Publication Year: 2011; Volume 173
ISBNs: 978-0-8218-4911-8 (print); 978-1-4704-1400-9 (online)
DOI: https://doi.org/10.1090/surv/173
MathSciNet review: 2760023
MSC: Primary 68U05; Secondary 52B55, 52C07, 68P05, 68W25

View full volume as PDF

Read more about this volume

Table of Contents

Download chapters as PDF

Front/Back Matter

• View this volume's front and back matter

Chapters

• 1. The power of grids—closest pair and smallest enclosing disk
• 2. Quadtrees—hierarchical grids
• 3. Well-separated pair decomposition
• 4. Clustering—definitions and basic algorithms
• 5. On complexity, sampling, and $\varepsilon$-nets and $\varepsilon$-samples
• 6. Approximation via reweighting
• 7. Yet even more on sampling
• 8. Sampling and the moments technique
• 9. Depth estimation via sampling
• 10. Approximating the depth via sampling and emptiness
• 11. Random partition via shifting
• 12. Good triangulations and meshing
• 13. Approximating the Euclidean traveling salesman problem (TSP)
• 14. Approximating the Euclidean TSP using bridges
• 15. Linear programming in low dimensions
• 16. Polyhedrons, polytopes, and linear programming
• 17. Approximate nearest neighbor search in low dimension
• 18. Approximate nearest neighbor via point-location
• 19. Dimension Reducation - The Johnson-Lindenstrauss (JL)lemma
• 20. Approximate nearest neighbor (ANN) search in high dimensions
• 21. Approximating a convex body by an ellipsoid
• 22. Approximating the minimum volume bounding box of a point set
• 23. Coresets
• 24. Approximation using shell sets
• 25. Duality
• 26. Finite metric spaces and partitions
• 27. Some probability and tail inequalities
• 28. Miscellaneous prerequisite