Geometric approximation algorithms / Sariel Har-Peled.

Format:

Book

Author/Creator:

Har-Peled, Sariel, 1971- author.

Series:

Mathematical surveys and monographs ; Volume 173.

Mathematical surveys and monographs ; Volume 173

Language:

English

Subjects (All):

Approximation algorithms.

Geometry--Data processing.

Geometry.

Computer graphics.

Discrete geometry.

Physical Description:

1 online resource (xii, 362 pages) : illustrations.

Edition:

1st ed.

Place of Publication:

Providence, Rhode Island : American Mathematical Society, [2011]

Language Note:

English

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.

Contents:

Cover

Title page

Contents

Preface

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 -nets and -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

Back Cover.

Notes:

Bibliographic Level Mode of Issuance: Monograph

Includes bibliographical references (pages 349-356) and index.

Description based on print version record.

Description based on publisher supplied metadata and other sources.

ISBN:

1-4704-1400-7

OCLC:

898200174