Geometric Approximation Algorithms (Mathematical Surveys and Monographs) (Mathematical Surveys and Monographs, 173)

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 Cover 1 Title page 4 Contents 6 Preface 12 The power of grids—closest pair and smallest enclosing disk 14 Quadtrees—hierarchical grids 26 Well-separated pair decomposition 42 Clustering—definitions and basic algorithms 60 On complexity, sampling, and ε-nets and ε-samples 74 Approximation via reweighting 100 Yet even more on sampling 116 Sampling and the moments technique 134 Depth estimation via sampling 148 Approximating the depth via sampling and emptiness 158 Random partition via shifting 164 Good triangulations and meshing 176 Approximating the Euclidean traveling salesman problem (TSP) 190 Approximating the Euclidean TSP using bridges 204 Linear programming in low dimensions 216 Polyhedrons, polytopes, and linear programming 230 Approximate nearest neighbor search in low dimension 246 Approximate nearest neighbor via point-location 256 The Johnson-Lindenstrauss lemma 270 Approximate nearest neighbor (ANN) search in high dimensions 282 Approximating a convex body by an ellipsoid 292 Approximating the minimum volume bounding box of a point set 296 Coresets 304 Approximation using shell sets 320 Duality 328 Finite metric spaces and partitions 336 Some probability and tail inequalities 348 Miscellaneous prerequisite 360 Bibliography 362 Index 370 Back Cover 378 Covers geometric approximation algorithms in detail. In addition, more traditional computational geometry techniques that are widely used in developing such algorithms, such as sampling and linear programming are also surveyed. Other topics covered include approximate nearest-neighbour search, shape approximation, coresets, dimension reduction, and embeddings.