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 *