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.
Author(s): Giri Narasimhan, Michiel Smid
Publisher: Cambridge University Press
Year: 2007
Language: English
Pages: 518
Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 15
Acknowledgments......Page 16
PART I Preliminaries......Page 19
1.1 What is this book about?......Page 21
1.1.1 Spanning trees......Page 24
1.1.2 Steiner trees......Page 25
1.1.4 Triangulations......Page 26
1.2 The topic of this book: Spanners......Page 27
1.3 Using spanners to approximate minimum spanning trees......Page 29
1.4 A simple greedy spanner algorithm......Page 30
Exercises......Page 31
Bibliographic notes......Page 33
2.1 Algorithms and data structures......Page 36
2.2.1 Graphs......Page 37
2.2.4 Representing graphs......Page 38
2.3.2 Lowest common ancestors......Page 39
Reduction to the range minimum problem......Page 42
Solving the range minimum problem......Page 44
2.3.4 Centroids and separators in trees......Page 47
2.4 Coloring graphs of bounded degree......Page 48
2.5.1 Algorithm SingleSource......Page 49
2.5.2 The correctness proof of algorithm SingleSource......Page 50
2.6 Minimum spanning trees......Page 53
2.6.1 Kruskal’s algorithm......Page 54
2.6.2 Prim’s algorithm......Page 55
Exercises......Page 56
Bibliographic notes......Page 57
3.1 Algebraic computation-trees......Page 59
3.3 Lower bounds for algebraic decision tree algorithms......Page 61
3.3.1 Linear decision trees......Page 62
3.3.2 The general lower bound......Page 64
3.3.3 Some applications......Page 68
3.4.1 A reduction from the element uniqueness problem......Page 69
3.4.2 A lower bound for a set of pairwise distinct points......Page 70
Algorithm B......Page 71
Algorithm D......Page 72
Analysis of algorithm D......Page 73
Exercises......Page 75
Bibliographic notes......Page 76
PART II Spanners Based on Simplicial Cones......Page 79
4.1 The Theta-graph......Page 81
4.1.1 Bounding the stretch factor of the Theta-graph......Page 83
4.1.2 Constructing the Theta-graph......Page 87
Finding the leftmost point in a translated query halfplane......Page 88
Computing all edges of (S, κ) corresponding to a cone......Page 89
4.2 A spanner of bounded degree......Page 91
4.2.1 Sink spanners......Page 92
4.2.2 The transformation......Page 94
4.3 Generalizing skip lists: A spanner with logarithmic spanner diameter......Page 96
4.3.1 Skip lists......Page 97
4.3.2 The skip list spanner......Page 99
Analyzing one level of the skip list spanner......Page 104
Completing the proof......Page 106
Exercises......Page 107
Bibliographic notes......Page 109
5.1 Simplicial cones and frames......Page 110
5.2.1 Covering Rd by cones......Page 111
5.2.2 Triangulating a hypercube......Page 113
5.2.3 Refining the cones in B to simplicial cones......Page 115
5.3 Applications of Theta-frames......Page 116
5.4 Range trees......Page 117
5.4.1 Answering range queries......Page 119
5.4.2 Supporting deletions......Page 120
5.5 Higher-dimensional Theta-graphs......Page 121
5.5.2 The d-dimensional sink spanner......Page 122
5.5.4 A d-dimensional spanner of bounded degree......Page 123
Exercises......Page 124
Bibliographic notes......Page 125
6 Geometric Analysis: The Gap Property......Page 126
6.1 The gap property......Page 127
6.2 A lower bound......Page 129
6.3 An upper bound for points in the unit cube......Page 130
6.4 A useful geometric lemma......Page 132
6.5 Worst-case analysis of the 2-Opt algorithm for the traveling salesperson problem......Page 134
Exercises......Page 136
Bibliographic notes......Page 137
7.1 A sufficient condition for “spannerhood”......Page 138
7.2 The gap-greedy algorithm......Page 139
7.3 Toward an efficient implementation......Page 142
7.4 An efficient implementation of the gap-greedy algorithm......Page 146
7.4.1 The main data structure......Page 147
The layer 1 tree......Page 148
The third layer of the data structure......Page 149
The operations ForbidSource and ForbidSink......Page 150
7.4.2 The final algorithm......Page 151
7.5 Generalization to higher dimensions......Page 155
Bibliographic notes......Page 156
8.1 Approximate distance enumeration......Page 157
8.2 Exact distance enumeration......Page 160
8.3 Using the gap-greedy spanner......Page 162
Bibliographic notes......Page 164
PART III The Well-Separated Pair Decomposition and Its Applications......Page 167
9.1 Definition of the well-separated pair decomposition......Page 169
9.2 Spanners based on the well-separated pair decomposition......Page 172
9.3.1 Definition of the split tree......Page 173
9.3.2 Computing the split tree in O(n log n) time......Page 176
9.4 Computing the well-separated pair decomposition......Page 180
9.4.1 The analysis of algorithm ComputeWSPD......Page 182
9.5 Finding the pair that separates two points......Page 186
9.5.1 Answering pair queries using centroid edges......Page 187
9.5.2 Answering pair queries using a path decomposition......Page 188
9.6 Extension to other metrics......Page 190
9.6.1 The unit disk metric......Page 191
Exercises......Page 192
Bibliographic notes......Page 194
10.1.1 The first construction......Page 196
10.1.2 The second construction......Page 198
10.2 A spanner with logarithmic spanner diameter......Page 202
10.3.1 The closest pair problem......Page 204
10.3.2 Computing closest pairs......Page 205
10.3.3 The all-nearest neighbors problem......Page 208
10.3.4 Computing an approximate minimum spanning tree......Page 211
Exercises......Page 212
Bibliographic notes......Page 213
11.1 Chapter overview......Page 214
11.2 Dumbbells......Page 215
11.3 A packing result for dumbbells......Page 216
11.4 Establishing the length-grouping property......Page 220
11.5.1 Dumbbells of approximately the same length......Page 223
11.5.2 The general case......Page 224
11.6 Dumbbell trees......Page 225
11.7 Constructing the dumbbell trees......Page 227
11.8 The dumbbell trees constitute a spanner......Page 228
11.9 The Dumbbell Theorem......Page 233
Bibliographic notes......Page 235
12.1 Shortcutting trees......Page 237
12.1.1 Monotone diameters 1 and 2......Page 238
12.1.2 Monotone diameter 3......Page 239
Existence of cut vertices......Page 240
Connecting the vertices of T to the cut vertices......Page 242
12.1.3 Generalization to larger monotone diameters......Page 245
12.1.4 The Ackermann function and its inverse......Page 246
12.1.5 Monotone diameter 2k......Page 251
12.1.6 Shortcutting trees using O(n) edges......Page 255
12.2 Spanners with low spanner diameter......Page 256
Bibliographic notes......Page 258
13 Approximating the Stretch Factor of Euclidean Graphs......Page 260
13.1 The first approximation algorithm......Page 261
Approximating the stretch factor of a path......Page 262
Approximating the stretch factor of a tree......Page 263
13.2 A faster approximation algorithm......Page 266
13.2.1 The reduction......Page 268
Paths, cycles, and trees......Page 269
General Euclidean graphs......Page 270
Exercises......Page 271
Bibliographic notes......Page 272
PART IV The Path-Greedy Algorithm and Its Analysis......Page 273
14.1 Introduction and motivation......Page 275
14.2 Relation to the gap property......Page 277
14.3 A sufficient condition for the leapfrog property......Page 278
14.4.1 Overview of the proof of the Leapfrog Theorem......Page 280
14.5.1 Near-parallel......Page 282
14.5.3 Nested-dumbbells......Page 283
14.5.4 Lateral and non-lateral edges......Page 289
14.6 Bounding the weight of non-lateral edges......Page 291
14.6.1 The invariant P......Page 293
14.6.2 Processing one edge of E......Page 294
14.6.3 The charging path for edge e......Page 295
14.6.4 A digression: two lemmas on intervals......Page 298
14.6.5 Choosing a subset…......Page 300
14.6.6 Decomposing the charging path P......Page 304
14.6.7 The analysis of Phi......Page 307
14.6.8 Contradicting the leapfrog property......Page 313
14.7 Bounding the weight of lateral edges......Page 315
14.7.1 The invariant Q......Page 316
14.7.2 Processing one edge of E......Page 318
14.7.3 Analyzing the radial weight of T ......Page 319
14.7.4 Property Q.3 is maintained......Page 322
14.7.5 Property Q.4 is maintained......Page 323
14.8 Completing the proof of the Leapfrog Theorem......Page 324
14.9 A variant of the leapfrog property......Page 325
14.10 The Sparse Ball Theorem......Page 327
14.10.1 A recurrence relation for the number of Steiner points......Page 328
14.10.2 Applying the recurrence relation......Page 330
Exercises......Page 333
Bibliographic notes......Page 335
15 The Path-Greedy Algorithm......Page 336
15.1.1 Preliminary analysis of the path-greedy spanner......Page 337
15.1.2 Probabilistic analysis of the path-greedy spanner......Page 339
15.1.3 Improved weight analysis of the path-greedy spanner......Page 343
15.2.1 Overview of an improved path-greedy algorithm......Page 345
Speeding up distance computations......Page 347
15.2.2 Clustering weighted graphs......Page 348
15.2.3 The cluster graph H approximates G......Page 350
15.2.4 Cluster graphs of partial spanners......Page 356
15.2.5 Clustering algorithms for partial spanners......Page 358
15.2.6 The fast spanner algorithm......Page 363
15.2.7 The correctness proof of algorithm FastPathGreedy......Page 365
15.2.8 The weight analysis of the spanner......Page 366
15.2.9 The running time of algorithm FastPathGreedy......Page 368
15.3.1 Overview of the algorithm......Page 371
15.3.2 The integer weight functions......Page 373
15.3.3 Some packing results......Page 375
15.3.4 A multiple-sources shortest paths algorithm......Page 377
15.3.5 Computing a cluster cover and the cluster graph......Page 380
15.3.6 Computing the cluster centers......Page 382
15.3.7 Recomputing the cluster centers......Page 383
The third stage......Page 386
Overview of the third stage......Page 389
15.3.8 Answering short-path queries......Page 391
15.3.9 The fast spanner algorithm......Page 392
15.3.10 The correctness proof......Page 394
15.3.11 The weight analysis......Page 395
15.3.12 The running time......Page 397
Exercises......Page 399
Bibliographic notes......Page 400
PART V Further Results on Spanners and Applications......Page 401
16 The Distance Range Hierarchy......Page 403
16.1.1 Partitioning the edge set E......Page 404
16.1.2 A hierarchy of Euclidean graphs......Page 406
16.1.3 Properties of the hierarchical decomposition......Page 408
16.1.4 Querying the hierarchical decomposition......Page 413
16.1.5 The graphs Gi approximate the spanner G......Page 414
16.1.6 Summarizing the hierarchical decomposition......Page 417
16.2 The distance range hierarchy for point sets......Page 418
16.3.1 A general framework for pruning spanners......Page 419
16.3.2 A pruning algorithm based on well-separated pairs......Page 421
16.3.3 Setting the stage for the distance range hierarchy......Page 422
16.3.4 A pruning algorithm based on the distance range hierarchy......Page 424
16.4 The distance range hierarchy for spanners......Page 426
16.4.1 The partial spanners G'i......Page 427
16.4.3 The main result......Page 429
Bibliographic notes......Page 431
17 Approximating Shortest Paths in Spanners......Page 433
17.2 Approximate shortest path queries for points that are separated......Page 434
17.2.1 The general approach......Page 435
17.2.2 The data structure......Page 437
17.3.1 Computing the distance range hierarchy for G......Page 440
17.3.3 Answering approximate shortest path queries in G......Page 441
17.4 An application: Approximating the stretch factor of Euclidean graphs......Page 443
Bibliographic notes......Page 444
18.1 Definition of a fault-tolerant spanner......Page 445
18.2 Vertex fault-tolerance is equivalent to fault-tolerance......Page 447
18.3 A simple transformation......Page 448
18.4.1 Definition of the graph G......Page 452
18.4.2 The graph G is a (k, t)-FTS......Page 453
18.4.3 Constructing the graph G......Page 454
18.6 Fault-tolerant spanners of low degree and low weight......Page 455
18.6.2 Bounding the degree of the fault-tolerant path-greedy spanner......Page 456
18.6.3 Bounding the weight of the fault-tolerant path-greedy spanner......Page 457
Exercises......Page 459
Bibliographic notes......Page 460
19.1 The generic polynomial-time approximation scheme......Page 461
19.2 The perturbation step......Page 462
19.3 The sparse graph computation step......Page 464
19.4 The quadtree construction step......Page 466
19.5 A digression: Constructing a light graph of low weight......Page 468
19.6 The patching step......Page 472
19.7 The dynamic programming step......Page 482
Exercises......Page 484
Bibliographic notes......Page 485
20.1 Spanners of low degree......Page 486
20.2 Spanners with few edges......Page 487
20.3 Plane spanners......Page 488
20.4 Spanners among obstacles......Page 490
20.5 Single-source spanners......Page 491
20.8 Shortcuts......Page 492
20.9 Detour......Page 494
20.11 Optimization problems......Page 495
20.12 Experimental work......Page 496
20.13 Two more open problems......Page 497
20.14 Open problems from previous chapters......Page 498
Exercises......Page 499
Bibliography......Page 501
Algorithms Index......Page 513
Index......Page 514
