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