7/12/2011
Written by
A new text on geometric approximation algorithms authored by University of Illinois computer science professor Sariel Har-Peled is the first to cover the subject in detail. Geometric Approximation Algorithms describes key techniques in geometric approximation algorithms and also surveys some of the more traditional computational geometry techniques, such as sampling and linear programming.
The field of geometric approximation algorithms is a subfield of both computational geometry and approximation algorithms, explains Har-Peled.
“Exact algorithms for dealing with geometric objects are complicated, hard to implement in practice, and slow,” says Har-Peled. “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.”
What began as a collection of class notes on the subject was expanded by Har-Peled into his full length text. While writing the text, Har-Peled took a different approach than that used by other texts on computational geometry. In the book, Har-Peled unified several data-structures to use compressed quadtrees as the basic building block and provides an elaborate introduction to VC dimension, a subject he says can often be “somewhat mysterious.” In addition, the text covers some topics, including locality sensitive hashing and metric space partitions, that are not part of traditional computational geometry.