| |

| |

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 | |