
Preface  Table of Contents  Supplementary Material 
Mathematical Surveys and Monographs 2011; 362 pp; hardcover Volume: 173 ISBN10: 0821849115 ISBN13: 9780821849118 List Price: US$103 Member Price: US$82.40 Order Code: SURV/173 See also: Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures  Janos Pach and Micha Sharir  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 nearestneighbor 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. 


AMS Home 
Comments: webmaster@ams.org © Copyright 2014, American Mathematical Society Privacy Statement 