Published by
Cambridge University Press
in January 2007.
Description:
Aimed at an audience of researchers and graduate students in
computational geometry and algorithm design, this book uses the
Geometric Spanner Network Problem to showcase a number of useful
algorithmic techniques, data structure strategies, and geometric
analysis techniques with many applications, practical and theoretical.
The authors present rigorous descriptions of the main algorithms and
their analyses for different variations of the Geometric Spanner
Network Problem. Though the basic ideas behind most of these algorithms
are intuitive, very few are easy to describe and analyze. For most of
the algorithms, nontrivial data structures need to be designed, and
nontrivial techniques need to be developed in order for analysis to take
place. Still, there are several basic principles and results that are
used throughout the book. One of the most important is the powerful
well-separated pair decomposition. This decomposition is used as
a starting point for several of the spanner constructions.
Geometric Spanner Networks