Skip to content

Geometric Spanner Networks

ISBN-10: 0521815134

ISBN-13: 9780521815130

Edition: 2007

Authors: Giri Narasimhan, Michiel Smid

List price: $180.00
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

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.
Customers also bought

Book details

List price: $180.00
Copyright year: 2007
Publisher: Cambridge University Press
Publication date: 1/8/2007
Binding: Hardcover
Pages: 516
Size: 7.00" wide x 10.00" long x 1.25" tall
Weight: 2.332
Language: English

Giri Narasimhan earned a B.Tech. in Electrical Engineering from the Indian Institute of Technology in Mumbai, India, and a Ph.D. in Computer Science from the University of Wisconsin in Madison, Wisconsin, USA. He was a member of the faculty at the University of Memphis, and is currently at Florida International University.

Preface
Preliminaries
Introduction
What is this book about?
The topic of this book: Spanners
Using spanners to approximate minimum spanning trees
A simple greedy spanner algorithm
Exercises
Bibliographic notes
Algorithms and Graphs
Algorithms and data structures
Some notions from graph theory
Some algorithms on trees
Coloring graphs of bounded degree
Dijkstra's shortest paths algorithm
Minimum spanning trees
Exercises
Bibliographic notes
The Algebraic Computation-Tree Model
Algebraic computation-trees
Algebraic decision trees
Lower bounds for algebraic decision tree algorithms
A lower bound for constructing spanners
Exercises
Bibliographic notes
Spanners Based on Simplicial Cones
Spanners Based on the [Theta]-Graph
The [Theta]-graph
A spanner of bounded degree
Generalizing skip lists: A spanner with logarithmic spanner diameter
Exercises
Bibliographic notes
Cones in Higher Dimensional Space and [Theta]-Graphs
Simplicial cones and frames
Constructing a [theta]-frame
Applications of [theta]-frames
Range trees
Higher-dimensional [Theta]-graphs
Exercises
Bibliographic notes
Geometric Analysis: The Gap Property
The gap property
A lower bound
An upper bound for points in the unit cube
A useful geometric lemma
Worst-case analysis of the 2-Opt algorithm for the traveling salesperson problem
Exercises
Bibliographic notes
The Gap-Greedy Algorithm
A sufficient condition for "spannerhood"
The gap-greedy algorithm
Toward an efficient implementation
An efficient implementation of the gap-greedy algorithm
Generalization to higher dimensions
Exercises
Bibliographic notes
Enumerating Distances Using Spanners of Bounded Degree
Approximate distance enumeration
Exact distance enumeration
Using the gap-greedy spanner
Exercises
Bibliographic notes
The Well-Separated Pair Decomposition and Its Applications
The Well-Separated Pair Decomposition
Definition of the well-separated pair decomposition
Spanners based on the well-separated pair decomposition
The split tree
Computing the well-separated pair decomposition
Finding the pair that separates two points
Extension to other metrics
Exercises
Bibliographic notes
Applications of Well-Separated Pairs
Spanners of bounded degree
A spanner with logarithmic spanner diameter
Applications to other proximity problems
Exercises
Bibliographic notes
The Dumbbell Theorem
Chapter overview
Dumbbells
A packing result for dumbbells
Establishing the length-grouping property
Establishing the empty-region property
Dumbbell trees
Constructing the dumbbell trees
The dumbbell trees constitute a spanner
The Dumbbell Theorem
Exercises
Bibliographic notes
Shortcutting Trees and Spanners with Low Spanner Diameter
Shortcutting trees
Spanners with low spanner diameter
Exercises
Bibliographic notes
Approximating the Stretch Factor of Euclidean Graphs
The first approximation algorithm
A faster approximation algorithm
Exercises
Bibliographic notes
The Path-Greedy Algorithm and Its Analysis
Geometric Analysis: The Leapfrog Property
Introduction and motivation
Relation to the gap property
A sufficient condition for the leapfrog property
The Leapfrog Theorem
The cleanup phase
Bounding the weight of non-lateral edges
Bounding the weight of lateral edges
Completing the proof of the Leapfrog Theorem
A variant of the leapfrog property
The Sparse Ball Theorem
Exercises
Bibliographic notes
The Path-Greedy Algorithm
Analysis of the simple greedy algorithm PathGreedy
An efficient implementation of algorithm PathGreedy
A faster algorithm that uses indirect addressing
Exercises
Bibliographic notes
Further Results on Spanners and Applications
The Distance Range Hierarchy
The basic hierarchical decomposition
The distance range hierarchy for point sets
An application: Pruning spanners
The distance range hierarchy for spanners
Exercises
Bibliographic notes
Approximating Shortest Paths in Spanners
Bucketing distances
Approximate shortest path queries for points that are separated
Arbitrary approximate shortest path queries
An application: Approximating the stretch factor of Euclidean graphs
Exercises
Bibliographic notes
Fault-Tolerant Spanners
Definition of a fault-tolerant spanner
Vertex fault-tolerance is equivalent to fault-tolerance
A simple transformation
Fault-tolerant spanners based on well-separated pairs
Fault-tolerant spanners with O(kn) edges
Fault-tolerant spanners of low degree and low weight
Exercises
Bibliographic notes
Designing Approximation Algorithms with Spanners
The generic polynomial-time approximation scheme
The perturbation step
The sparse graph computation step
The quadtree construction step
A digression: Constructing a light graph of low weight
The patching step
The dynamic programming step
Exercises
Bibliographic notes
Further Results and Open Problems
Spanners of low degree
Spanners with few edges
Plane spanners
Spanners among obstacles
Single-source spanners
Locating centers
Decreasing the stretch factor
Shortcuts
Detour
External memory algorithms
Optimization problems
Experimental work
Two more open problems
Open problems from previous chapters
Exercises
Bibliography
Algorithms Index
Index