**Mathematical Surveys and Monographs**

Volume: 173;
2011;
362 pp;
Hardcover

MSC: Primary 68;
Secondary 52

Print ISBN: 978-0-8218-4911-8

Product Code: SURV/173

List Price: $103.00

Individual Member Price: $82.40

**Electronic ISBN: 978-1-4704-1400-9
Product Code: SURV/173.E**

List Price: $103.00

Individual Member Price: $82.40

#### You may also like

#### Supplemental Materials

# Geometric Approximation Algorithms

Share this page
*Sariel Har-Peled*

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.

#### Table of Contents

# Table of Contents

## Geometric Approximation Algorithms

- Cover Cover11 free
- Title page iii4 free
- Contents v6 free
- Preface xi12 free
- The power of grids—closest pair and smallest enclosing disk 114 free
- Quadtrees—hierarchical grids 1326
- Well-separated pair decomposition 2942
- Clustering—definitions and basic algorithms 4760
- On complexity, sampling, and 𝜖-nets and 𝜖-samples 6174
- Approximation via reweighting 87100
- Yet even more on sampling 103116
- Sampling and the moments technique 121134
- Depth estimation via sampling 135148
- Approximating the depth via sampling and emptiness 145158
- Random partition via shifting 151164
- Good triangulations and meshing 163176
- Approximating the Euclidean traveling salesman problem (TSP) 177190
- Approximating the Euclidean TSP using bridges 191204
- Linear programming in low dimensions 203216
- Polyhedrons, polytopes, and linear programming 217230
- Approximate nearest neighbor search in low dimension 233246
- Approximate nearest neighbor via point-location 243256
- The Johnson-Lindenstrauss lemma 257270
- Approximate nearest neighbor (ANN) search in high dimensions 269282
- Approximating a convex body by an ellipsoid 279292
- Approximating the minimum volume bounding box of a point set 283296
- Coresets 291304
- Approximation using shell sets 307320
- Duality 315328
- Finite metric spaces and partitions 323336
- Some probability and tail inequalities 335348
- Miscellaneous prerequisite 347360
- Bibliography 349362
- Index 357370 free
- Back Cover Back Cover1378

#### Readership

Graduate students and research mathematicians interested in the theory and practice of computational geometry.