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.

Giri Narasimhan is a member of the faculty at the University of Memphis, Tennessee, and is currently a professor in the School of Computing and information Sciences at Florida international university in Miami.

Preface	p. xiii
Preliminaries
Introduction	p. 3
What is this book about?	p. 3
The topic of this book: Spanners	p. 9
Using spanners to approximate minimum spanning trees	p. 11
A simple greedy spanner algorithm	p. 12
Exercises	p. 13
Bibliographic notes	p. 15
Algorithms and Graphs	p. 18
Algorithms and data structures	p. 18
Some notions from graph theory	p. 19
Some algorithms on trees	p. 21
Coloring graphs of bounded degree	p. 30
Dijkstra's shortest paths algorithm	p. 31
Minimum spanning trees	p. 35
Exercises	p. 38
Bibliographic notes	p. 39
The Algebraic Computation-Tree Model	p. 41
Algebraic computation-trees	p. 41
Algebraic decision trees	p. 43
Lower bounds for algebraic decision tree algorithms	p. 43
A lower bound for constructing spanners	p. 51
Exercises	p. 57
Bibliographic notes	p. 58
Spanners Based on Simplicial Cones
Spanners Based on the [Theta]-Graph	p. 63
The [Theta]-graph	p. 63
A spanner of bounded degree	p. 73
Generalizing skip lists: A spanner with logarithmic spanner diameter	p. 78
Exercises	p. 89
Bibliographic notes	p. 90
Cones in Higher Dimensional Space and [Theta]-Graphs	p. 92
Simplicial cones and frames	p. 92
Constructing a [theta]-frame	p. 93
Applications of [theta]-frames	p. 98
Range trees	p. 99
Higher-dimensional [Theta]-graphs	p. 103
Exercises	p. 106
Bibliographic notes	p. 106
Geometric Analysis: The Gap Property	p. 108
The gap property	p. 109
A lower bound	p. 111
An upper bound for points in the unit cube	p. 112
A useful geometric lemma	p. 114
Worst-case analysis of the 2-Opt algorithm for the traveling salesperson problem	p. 116
Exercises	p. 118
Bibliographic notes	p. 118
The Gap-Greedy Algorithm	p. 120
A sufficient condition for "spannerhood"	p. 120
The gap-greedy algorithm	p. 121
Toward an efficient implementation	p. 124
An efficient implementation of the gap-greedy algorithm	p. 128
Generalization to higher dimensions	p. 137
Exercises	p. 137
Bibliographic notes	p. 138
Enumerating Distances Using Spanners of Bounded Degree	p. 139
Approximate distance enumeration	p. 139
Exact distance enumeration	p. 142
Using the gap-greedy spanner	p. 144
Exercises	p. 145
Bibliographic notes	p. 146
The Well-Separated Pair Decomposition and Its Applications
The Well-Separated Pair Decomposition	p. 151
Definition of the well-separated pair decomposition	p. 151
Spanners based on the well-separated pair decomposition	p. 154
The split tree	p. 155
Computing the well-separated pair decomposition	p. 162
Finding the pair that separates two points	p. 168
Extension to other metrics	p. 172
Exercises	p. 174
Bibliographic notes	p. 175
Applications of Well-Separated Pairs	p. 178
Spanners of bounded degree	p. 178
A spanner with logarithmic spanner diameter	p. 184
Applications to other proximity problems	p. 186
Exercises	p. 194
Bibliographic notes	p. 195
The Dumbbell Theorem	p. 196
Chapter overview	p. 196
Dumbbells	p. 197
A packing result for dumbbells	p. 198
Establishing the length-grouping property	p. 202
Establishing the empty-region property	p. 205
Dumbbell trees	p. 207
Constructing the dumbbell trees	p. 209
The dumbbell trees constitute a spanner	p. 210
The Dumbbell Theorem	p. 215
Exercises	p. 217
Bibliographic notes	p. 217
Shortcutting Trees and Spanners with Low Spanner Diameter	p. 219
Shortcutting trees	p. 219
Spanners with low spanner diameter	p. 238
Exercises	p. 240
Bibliographic notes	p. 240
Approximating the Stretch Factor of Euclidean Graphs	p. 242
The first approximation algorithm	p. 243
A faster approximation algorithm	p. 248
Exercises	p. 253
Bibliographic notes	p. 253
The Path-Greedy Algorithm and Its Analysis
Geometric Analysis: The Leapfrog Property	p. 257
Introduction and motivation	p. 257
Relation to the gap property	p. 259
A sufficient condition for the leapfrog property	p. 260
The Leapfrog Theorem	p. 262
The cleanup phase	p. 264
Bounding the weight of non-lateral edges	p. 273
Bounding the weight of lateral edges	p. 297
Completing the proof of the Leapfrog Theorem	p. 306
A variant of the leapfrog property	p. 307
The Sparse Ball Theorem	p. 309
Exercises	p. 315
Bibliographic notes	p. 317
The Path-Greedy Algorithm	p. 318
Analysis of the simple greedy algorithm PathGreedy	p. 319
An efficient implementation of algorithm PathGreedy	p. 327
A faster algorithm that uses indirect addressing	p. 353
Exercises	p. 381
Bibliographic notes	p. 382
Further Results on Spanners and Applications
The Distance Range Hierarchy	p. 385
The basic hierarchical decomposition	p. 386
The distance range hierarchy for point sets	p. 400
An application: Pruning spanners	p. 401
The distance range hierarchy for spanners	p. 408
Exercises	p. 413
Bibliographic notes	p. 413
Approximating Shortest Paths in Spanners	p. 415
Bucketing distances	p. 416
Approximate shortest path queries for points that are separated	p. 416
Arbitrary approximate shortest path queries	p. 422
An application: Approximating the stretch factor of Euclidean graphs	p. 425
Exercises	p. 426
Bibliographic notes	p. 426
Fault-Tolerant Spanners	p. 427
Definition of a fault-tolerant spanner	p. 427
Vertex fault-tolerance is equivalent to fault-tolerance	p. 429
A simple transformation	p. 430
Fault-tolerant spanners based on well-separated pairs	p. 434
Fault-tolerant spanners with O(kn) edges	p. 437
Fault-tolerant spanners of low degree and low weight	p. 437
Exercises	p. 441
Bibliographic notes	p. 441
Designing Approximation Algorithms with Spanners	p. 443
The generic polynomial-time approximation scheme	p. 443
The perturbation step	p. 444
The sparse graph computation step	p. 446
The quadtree construction step	p. 448
A digression: Constructing a light graph of low weight	p. 450
The patching step	p. 454
The dynamic programming step	p. 464
Exercises	p. 466
Bibliographic notes	p. 467
Further Results and Open Problems	p. 468
Spanners of low degree	p. 468
Spanners with few edges	p. 469
Plane spanners	p. 470
Spanners among obstacles	p. 472
Single-source spanners	p. 473
Locating centers	p. 474
Decreasing the stretch factor	p. 474
Shortcuts	p. 474
Detour	p. 476
External memory algorithms	p. 477
Optimization problems	p. 477
Experimental work	p. 478
Two more open problems	p. 479
Open problems from previous chapters	p. 480
Exercises	p. 481
Bibliography	p. 483
Algorithms Index	p. 495
Index	p. 496
Table of Contents provided by Ingram. All Rights Reserved.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Amazon no longer offers textbook rentals. We do!

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

Geometric Spanner Networks

9780521815130

0521815134

Supplemental Materials

Summary

Author Biography

Table of Contents

Supplemental Materials

Rewards Program