Geometric spanner networks / Giri Narasimhan, Michiel Smid.

Format:

Book

Author/Creator:

Narasimhan, Giri.

Contributor:

Smid, Michiel.

Hazel M. Hussong Fund.

Language:

English

Subjects (All):

Computer algorithms.

Trees (Graph theory)--Data processing.

Trees (Graph theory).

Geometry--Data processing.

Geometry.

Physical Description:

xv, 500 pages : illustrations ; 27 cm

Place of Publication:

Cambridge ; New York : Cambridge University Press, 2007.

Summary:

Aimed at an audience of researchers and graduate students in computational geometry and algorithm design, this book uses the Geometric Spanner Network Problem to show-case 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. Although 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.

Contents:

1.2 The topic of this book: Spanners 9

1.3 Using spanners to approximate minimum spanning trees 11

1.4 A simple greedy spanner algorithm 12

2 Algorithms and Graphs 18

2.1 Algorithms and data structures 18

2.2 Some notions from graph theory 19

2.3 Some algorithms on trees 21

2.4 Coloring graphs of bounded degree 30

2.5 Dijkstra's shortest paths algorithm 31

2.6 Minimum spanning trees 35

3 The Algebraic Computation-Tree Model 41

3.1 Algebraic computation-trees 41

3.2 Algebraic decision trees 43

3.3 Lower bounds for algebraic decision tree algorithms 43

3.4 A lower bound for constructing spanners 51

II Spanners Based on Simplicial Cones

4 Spanners Based on the [Theta]-Graph 63

4.1 The [Theta]-graph 63

4.2 A spanner of bounded degree 73

4.3 Generalizing skip lists: A spanner with logarithmic spanner diameter 78

5 Cones in Higher Dimensional Space and [Theta]-Graphs 92

5.1 Simplicial cones and frames 92

5.2 Constructing a [theta]-frame 93

5.3 Applications of [theta]-frames 98

5.4 Range trees 99

5.5 Higher-dimensional [Theta]-graphs 103

6 Geometric Analysis: The Gap Property 108

6.1 The gap property 109

6.2 A lower bound 111

6.3 An upper bound for points in the unit cube 112

6.4 A useful geometric lemma 114

6.5 Worst-case analysis of the 2-Opt algorithm for the traveling salesperson problem 116

7 The Gap-Greedy Algorithm 120

7.1 A sufficient condition for "spannerhood" 120

7.2 The gap-greedy algorithm 121

7.3 Toward an efficient implementation 124

7.4 An efficient implementation of the gap-greedy algorithm 128

7.5 Generalization to higher dimensions 137

8 Enumerating Distances Using Spanners of Bounded Degree 139

8.1 Approximate distance enumeration 139

8.2 Exact distance enumeration 142

8.3 Using the gap-greedy spanner 144

III The Well-Separated Pair Decomposition and Its Applications

9 The Well-Separated Pair Decomposition 151

9.1 Definition of the well-separated pair decomposition 151

9.2 Spanners based on the well-separated pair decomposition 154

9.3 The split tree 155

9.4 Computing the well-separated pair decomposition 162

9.5 Finding the pair that separates two points 168

9.6 Extension to other metrics 172

10 Applications of Well-Separated Pairs 178

10.1 Spanners of bounded degree 178

10.2 A spanner with logarithmic spanner diameter 184

10.3 Applications to other proximity problems 186

11 The Dumbbell Theorem 196

11.2 Dumbbells 197

11.3 A packing result for dumbbells 198

11.4 Establishing the length-grouping property 202

11.5 Establishing the empty-region property 205

11.6 Dumbbell trees 207

11.7 Constructing the dumbbell trees 209

11.8 The dumbbell trees constitute a spanner 210

11.9 The Dumbbell Theorem 215

12 Shortcutting Trees and Spanners with Low Spanner Diameter 219

12.1 Shortcutting trees 219

12.2 Spanners with low spanner diameter 238

13 Approximating the Stretch Factor of Euclidean Graphs 242

13.1 The first approximation algorithm 243

13.2 A faster approximation algorithm 248

IV The Path-Greedy Algorithm and Its Analysis

14 Geometric Analysis: The Leapfrog Property 257

14.1 Introduction and motivation 257

14.2 Relation to the gap property 259

14.3 A sufficient condition for the leapfrog property 260

14.4 The Leapfrog Theorem 262

14.5 The cleanup phase 264

14.6 Bounding the weight of non-lateral edges 273

14.7 Bounding the weight of lateral edges 297

14.8 Completing the proof of the Leapfrog Theorem 306

14.9 A variant of the leapfrog property 307

14.10 The Sparse Ball Theorem 309

15 The Path-Greedy Algorithm 318

15.1 Analysis of the simple greedy algorithm PathGreedy 319

15.2 An efficient implementation of algorithm PathGreedy 327

15.3 A faster algorithm that uses indirect addressing 353

V Further Results on Spanners and Applications

16 The Distance Range Hierarchy 385

16.1 The basic hierarchical decomposition 386

16.2 The distance range hierarchy for point sets 400

16.3 An application: Pruning spanners 401

16.4 The distance range hierarchy for spanners 408

17 Approximating Shortest Paths in Spanners 415

17.1 Bucketing distances 416

17.2 Approximate shortest path queries for points that are separated 416

17.3 Arbitrary approximate shortest path queries 422

17.4 An application: Approximating the stretch factor of Euclidean graphs 425

18 Fault-Tolerant Spanners 427

18.1 Definition of a fault-tolerant spanner 427

18.2 Vertex fault-tolerance is equivalent to fault-tolerance 429

18.3 A simple transformation 430

18.4 Fault-tolerant spanners based on well-separated pairs 434

18.5 Fault-tolerant spanners with O(kn) edges 437

18.6 Fault-tolerant spanners of low degree and low weight 437

19 Designing Approximation Algorithms with Spanners 443

19.1 The generic polynomial-time approximation scheme 443

19.2 The perturbation step 444

19.3 The sparse graph computation step 446

19.4 The quadtree construction step 448

19.5 A digression: Constructing a light graph of low weight 450

19.6 The patching step 454

19.7 The dynamic programming step 464

20 Further Results and Open Problems 468

20.1 Spanners of low degree 468

20.2 Spanners with few edges 469

20.3 Plane spanners 470

20.4 Spanners among obstacles 472

20.5 Single-source spanners 473

20.6 Locating centers 474

20.7 Decreasing the stretch factor 474

20.8 Shortcuts 474

20.9 Detour 476

20.10 External memory algorithms 477

20.11 Optimization problems 477

20.12 Experimental work 478

20.13 Two more open problems 479

20.14 Open problems from previous chapters 480.

Notes:

Includes bibliographical references (pages 483-494) and indexes.

Local Notes:

Acquired for the Penn Libraries with assistance from the Hazel M. Hussong Fund.

ISBN:

0521815134

9780521815130

OCLC:

71237379

Publisher Number:

9780521815130

Online:

Publisher description