Geometric approximation algorithms

By: Sariel Har-PeledMaterial type: TextTextSeries: Mathematical Surveys and Monographs ; Vol. 173Publication details: Rhode Island: American Mathematical Society, [c2011]Description: 362 pISBN: 978-0-8218-4911-8Subject(s): MathematicsLOC classification: QA448.D38
Contents:
1. The power of grids—closest pair and smallest enclosing disk 2. Quadtrees—hierarchical grids 3. Well-separated pair decomposition 4. Clustering—definitions and basic algorithms 5. On complexity, sampling, and ε-nets and ε-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 point-location 19. Dimension Reducation - The Johnson-Lindenstrauss (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
Summary: 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. --- summary provided by publisher
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current library Collection Shelving location Call number Status Notes Date due Barcode Item holds
Book Book ICTS
Mathematic Rack No 6 QA448.D38 (Browse shelf (Opens below)) Available Billno:IN 003 582; Billdate: 2018-01-11 00929
Total holds: 0

1. The power of grids—closest pair and smallest enclosing disk
2. Quadtrees—hierarchical grids
3. Well-separated pair decomposition
4. Clustering—definitions and basic algorithms
5. On complexity, sampling, and ε-nets and ε-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 point-location
19. Dimension Reducation - The Johnson-Lindenstrauss (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

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. --- summary provided by publisher

There are no comments on this title.

to post a comment.