# Geometric Spanner Networks

by Giri Narasimhan /
2007 / English / PDF

4.2 MB Download

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.

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.