Hardcover ISBN:  9780821849118 
Product Code:  SURV/173 
List Price:  $110.00 
MAA Member Price:  $99.00 
AMS Member Price:  $88.00 
Electronic ISBN:  9781470414009 
Product Code:  SURV/173.E 
List Price:  $103.00 
MAA Member Price:  $92.70 
AMS Member Price:  $82.40 

Book DetailsMathematical Surveys and MonographsVolume: 173; 2011; 362 ppMSC: Primary 68; Secondary 52;
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 nearestneighbor 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.ReadershipGraduate students and research mathematicians interested in the theory and practice of computational geometry.

Table of Contents

Chapters

1. The power of grids—closest pair and smallest enclosing disk

2. Quadtrees—hierarchical grids

3. Wellseparated 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 pointlocation

19. Dimension Reducation  The JohnsonLindenstrauss (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


Additional Material

Request Review Copy

Get Permissions
 Book Details
 Table of Contents
 Additional Material

 Request Review Copy
 Get Permissions
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 nearestneighbor 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.
Graduate students and research mathematicians interested in the theory and practice of computational geometry.

Chapters

1. The power of grids—closest pair and smallest enclosing disk

2. Quadtrees—hierarchical grids

3. Wellseparated 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 pointlocation

19. Dimension Reducation  The JohnsonLindenstrauss (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