Muutke küpsiste eelistusi

Geometric Spanner Networks [Kõva köide]

(Florida International University), (Carleton University, Ottawa)
  • Formaat: Hardback, 516 pages, kõrgus x laius x paksus: 260x185x34 mm, kaal: 1060 g
  • Ilmumisaeg: 08-Jan-2007
  • Kirjastus: Cambridge University Press
  • ISBN-10: 0521815134
  • ISBN-13: 9780521815130
Teised raamatud teemal:
Geometric Spanner NetworksSuurem pilt
  • Formaat: Hardback, 516 pages, kõrgus x laius x paksus: 260x185x34 mm, kaal: 1060 g
  • Ilmumisaeg: 08-Jan-2007
  • Kirjastus: Cambridge University Press
  • ISBN-10: 0521815134
  • ISBN-13: 9780521815130
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780521815130.html
Märksõnad:
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.

Rigorous descriptions and analyses of the main algorithms for different variations of the Geometric Spanner Network Problem.

Arvustused

"The writing style is clear, with a clean presentation enriched with boxes highlighting important contents and figures." David Orden, Mathematical Reviews

Muu info

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


Giri Narasimhan earned a B.Tech. in Electrical Engineering from the Indian Institute of Technology in Mumbai, India, and a Ph.D. in Computer Science from the University of Wisconsin in Madison, Wisconsin, USA. He was a member of the faculty at the University of Memphis, and is currently at Florida International University. Michiel Smid received a M.Sc. degree in Mathematics from the University of Technology in Eidenhoven and a Ph.D. degree in Computer Science from the University of Amsterdam. He has held teaching positions at the Max-Planck-Institute for Computer Science in Saarbrucken, King's College in London, and the University of Magdenburg. Since 2001, he has been at Carleton University, where he is currently a professor of Computer Science.