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