You are here

Geometric Approximation Algorithms

Sariel Har-Peled
Publisher: 
American Mathematical Society
Publication Date: 
2011
Number of Pages: 
362
Format: 
Hardcover
Series: 
Mathematical Surveys and Monogrpahs 173
Price: 
98.00
ISBN: 
9780821849118
Category: 
Monograph
We do not plan to review this book.
  • The power of grids--closest pair and smallest enclosing disk
  • Quadtrees--hierarchical grids
  • Well-separated pair decomposition
  • Clustering--definitions and basic algorithms
  • On complexity, sampling, and $\varepsilon$-nets and $\varepsilon$-samples
  • Approximation via reweighting
  • Yet even more on sampling
  • Sampling and the moments technique
  • Depth estimation via sampling
  • Approximating the depth via sampling and emptiness
  • Random partition via shifting
  • Good triangulations and meshing
  • Approximating the Euclidean traveling salesman problem (TSP)
  • Approximating the Euclidean TSP using bridges
  • Linear programming in low dimensions
  • Polyhedrons, polytopes, and linear programming
  • Approximate nearest neighbor search in low dimension
  • Approximate nearest neighbor via point-location
  • The Johnson-Lindenstrauss lemma
  • Approximate nearest neighbor (ANN) search in high dimensions
  • Approximating a convex body by an ellipsoid
  • Approximating the minimum volume bounding box of a point set
  • Coresets
  • Approximation using shell sets
  • Duality
  • Finite metric spaces and partitions
  • Some probability and tail inequalities
  • Miscellaneous prerequisite
  • Bibliography
  • Index