Geometric Approximation Algorithms
Sariel Har-Peled
180 x 240 mm
Year of Publishing
Territorial Rights
Orient BlackSwan

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


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


3-6-752 Himayatnagar, Hyderabad,
500 029 Telangana
Phone: (040) 27662849, 27662850
Follow us on
Copyright © Orient BlackSwan, All rights reserved.
Disclaimer and Privacy Policy
Terms and Conditions
Frequently Asked Questions