Geometric Spanner Networks

Aimed at an audience of researchers and graduate students in computationalgeometry and algorithm design this book uses the Geometric Spanner NetworkProblem to s... » 

Aimed at an audience of researchers and graduate students in computationalgeometry and algorithm design this book uses the Geometric Spanner NetworkProblem to showcase a number of useful algorithmic techniques data structurestrategies and geometric analysis techniques with many applications practicaland theoretical. The authors present rigorous descriptions of the mainalgorithms and their analyses for different variations of the Geometric SpannerNetwork Problem. Though the basic ideas behind most of these algorithms areintuitive very few are easy to describe and analyze. For most of thealgorithms nontrivial data structures need to be designed and nontrivialtechniques need to be developed in order for analysis to take place. Stillthere are several basic principles and results that are used throughout thebook. One of the most important is the powerful wellseparated pairdecomposition. This decomposition is used as a starting point for several ofthe spanner constructions. «