Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
The following link can be shared to navigate to this page. You can select the link to copy or click the 'Copy To Clipboard' button below.
Copy To Clipboard
Successfully Copied!
Geometric Approximation Algorithms
 
Sariel Har-Peled University of Illinois at Urbana-Champaign, Urbana, IL
Front Cover for Geometric Approximation Algorithms
Available Formats:
Hardcover ISBN: 978-0-8218-4911-8
Product Code: SURV/173
362 pp 
List Price: $110.00
MAA Member Price: $99.00
AMS Member Price: $88.00
Electronic ISBN: 978-1-4704-1400-9
Product Code: SURV/173.E
362 pp 
List Price: $103.00
MAA Member Price: $92.70
AMS Member Price: $82.40
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $165.00
MAA Member Price: $148.50
AMS Member Price: $132.00
Front Cover for Geometric Approximation Algorithms
Click above image for expanded view
  • Front Cover for Geometric Approximation Algorithms
  • Back Cover for Geometric Approximation Algorithms
Geometric Approximation Algorithms
Sariel Har-Peled University of Illinois at Urbana-Champaign, Urbana, IL
Available Formats:
Hardcover ISBN:  978-0-8218-4911-8
Product Code:  SURV/173
362 pp 
List Price: $110.00
MAA Member Price: $99.00
AMS Member Price: $88.00
Electronic ISBN:  978-1-4704-1400-9
Product Code:  SURV/173.E
362 pp 
List Price: $103.00
MAA Member Price: $92.70
AMS Member Price: $82.40
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $165.00
MAA Member Price: $148.50
AMS Member Price: $132.00
  • Book Details
     
     
    Mathematical Surveys and Monographs
    Volume: 1732011
    MSC: 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 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.

    Readership

    Graduate 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. Well-separated 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 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
  • Request Review Copy
  • Get Permissions
Volume: 1732011
MSC: 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 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.

Readership

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. Well-separated 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 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
You may be interested in...
Please select which format for which you are requesting permissions.