Geometric Spanner Networks Book

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