Exact algorithms for dealing with geometric objects are complicated, hard to implement in practice, and slow. Over the last 20 years a theory of geometric approximation algorithms has emerged. These algorithms tend to be simple, fast, and more robust than their exact counterparts.
This book is the first to cover geometric approximation algorithms in detail. In addition, more traditional computational geometry techniques that are widely used in developing such algorithms, like sampling, linear programming, etc., are also surveyed. Other topics covered include approximate nearest-neighbor search, shape approximation, coresets, dimension reduction, and embeddings. The topics covered are relatively independent and are supplemented by exercises. Close to 200 color figures are included in the text to illustrate proofs and ideas.
Sariel Har-Peled, University of Illinois at Urbana-Champaign, IL
Preface
Chapter 1. The Power of Grids – Closest Pair and Smallest Enclosing Disk 1.1. Preliminaries 1.2. Closest pair 1.3. A slow 2-approximation algorithm for the k-enclosing disk 1.4. A linear time 2-approximation for the k-enclosing disk 1.5. Bibliographical notes 1.6. Exercises
Chapter 2. Quadtrees – Hierarchical Grids 2.1. Quadtrees – a simple point-location data-structure 2.2. Compressed quadtrees 2.3. Dynamic quadtrees 2.4. Bibliographical notes 2.5. Exercises
Chapter 3. Well-Separated Pair Decomposition 3.1. Well-separated pair decomposition (WSPD) 3.2. Applications of WSPD 3.3. Semi-separated pair decomposition (SSPD) 3.4. Bibliographical notes 3.5. Exercises
Chapter 4. Clustering – Definitions and Basic Algorithms 4.1. Preliminaries 4.2. On k-center clustering 4.3. On k-median clustering 4.4. On k-means clustering 4.5. Bibliographical notes 4.6. Exercises
Chapter 5. On Complexity, Sampling, and e-Nets and e-Samples 5.1. VC dimension 5.2. Shattering dimension and the dual shattering dimension 5.3. On e-nets and e-sampling 5.4. Discrepancy 5.5. Proof of the e-net theorem 5.6. A better bound on the growth function 5.7. Bibliographical notes 5.8. Exercises
Chapter 6. Approximation via Reweighting 6.1. Preliminaries 6.2. Computing a spanning tree with low crossing number 6.3. Geometric set cover 6.4. Geometric set cover via linear programming 6.5. Bibliographical notes 6.6. Exercises Chapter 7. Yet Even More on Sampling 7.1. Introduction 7.2. Applications 7.3. Proof of Theorem 7.7 7.4. Bibliographical notes 7.5. Exercises
Chapter 8. Sampling and the Moments Technique 8.1. Vertical decomposition 8.2. General settings 8.3. Applications 8.4. Bounds on the probability of a region to be created 8.5. Bibliographical notes 8.6. Exercises
Chapter 9. Depth Estimation via Sampling 9.1. The at most k-levels 9.2. The crossing lemma 9.3. A general bound for the at most k-weight 9.4. Bibliographical notes 9.5. Exercises
Chapter 10. Approximating the Depth via Sampling and Emptiness 10.1. From emptiness to approximate range counting 10.2. Application: Halfplane and halfspace range counting 10.3. Relative approximation via sampling 10.4. Bibliographical notes 10.5. Exercises
Chapter 11. Random Partition via Shifting 11.1. Partition via shifting 11.2. Hierarchical representation of a point set 11.3. Low quality ANN search 11.4. Bibliographical notes 11.5. Exercises
Chapter 12. Good Triangulations and Meshing 12.1. Introduction – good triangulations 12.2. Triangulations and fat triangulations 12.3. Analysis 12.4. The result 12.5. Bibliographical notes
Chapter 13. Approximating the Euclidean Traveling Salesman Problem (TSP) 13.1. The TSP problem – introduction 13.2. When the optimal solution is friendly 13.3. TSP approximation via portals and sliding quadtrees 13.4. Bibliographical notes 13.5. Exercises
Chapter 14. Approximating the Euclidean TSP Using Bridges 14.1. Overview 14.2. Cuts and bridges 14.3. The dynamic programming 14.4. The result 14.5. Bibliographical notes
Chapter 15. Linear Programming in Low Dimensions 15.1. Linear programming 15.2. Low-dimensional linear programming 15.3. Linear programming with violations 15.4. Approximate linear programming with violations 15.5. LP-type problems 15.6. Bibliographical notes 15.7. Exercises
Chapter 16. Polyhedrons, Polytopes, and Linear Programming 16.1. Preliminaries 16.2. Properties of polyhedrons 16.3. Vertices of a polytope 16.4. Linear programming correctness 16.5. Bibliographical notes 16.6. Exercises
Chapter 17. Approximate Nearest Neighbor Search in Low Dimension 17.1. Introduction 17.2. The bounded spread case 17.3. ANN – the unbounded general case 17.4. Low quality ANN search via the ring separator tree 17.5. Bibliographical notes 17.6. Exercises
Chapter 18. Approximate Nearest Neighbor via Point-Location 18.1. ANN using point-location among balls 18.2. ANN using point-location among approximate balls 18.3. ANN using point-location among balls in low dimensions 18.4. Approximate Voronoi diagrams 18.5. Bibliographical notes 18.6. Exercises
Chapter 19. Dimension Reduction – The Johnson-Lindenstrauss (JL) Lemma 19.1. The Brunn-Minkowski inequality 19.2. Measure concentration on the sphere 19.3. Concentration of Lipschitz functions 19.4. The Johnson-Lindenstrauss lemma 19.5. Bibliographical notes 19.6. Exercises
Chapter 20. Approximate Nearest Neighbor (ANN) Search in High Dimensions 20.1. ANN on the hypercube 20.2. LSH and ANN in Euclidean space 20.3. Bibliographical notes Chapter 21. Approximating a Convex Body by an Ellipsoid 21.1. Ellipsoids 21.2. Bibliographical notes
Chapter 22. Approximating the Minimum Volume Bounding Box of a Point Set 22.1. Some geometry 22.2. Approximating the minimum volume bounding box 22.3. Exact algorithm for the minimum volume bounding box 22.4. Approximating the minimum volume bounding box in three dimensions 22.5. Bibliographical notes 22.6. Exercises
Chapter 23. Coresets 23.1. Coreset for directional width 23.2. Approximating the extent of lines and other creatures 23.3. Extent of polynomials 23.4. Roots of polynomials 23.5. Bibliographical notes 23.6. Exercises
Chapter 24. Approximation Using Shell Sets 24.1. Covering problems, expansion, and shell sets 24.2. Covering by cylinders 24.3. Bibliographical notes 24.4. Exercises
Chapter 25. Duality 25.1. Duality of lines and points 25.2. Higher dimensions 25.3. Bibliographical notes 25.4. Exercises
Chapter 26. Finite Metric Spaces and Partitions 26.1. Finite metric spaces 26.2. Random partitions 26.3. Probabilistic embedding into trees 26.4. Embedding any metric space into Euclidean space 26.5. Bibliographical notes 26.6. Exercises
Chapter 27. Some Probability and Tail Inequalities 27.1. Some probability background 27.2. Tail inequalities 27.3. Hoeffding’s inequality 27.4. Bibliographical notes 27.5. Exercises
Chapter 28. Miscellaneous Prerequisite 28.1. Geometry and linear algebra 28.2. Calculus
Bibliography Index