Geometric Spanner Networks

By: No Information Available

Write A Review

Hardcover | 8 January 2007

At a Glance

Hardcover
516 Pages

Dimensions(cm)
25.4 x 17.78 x 3.18

Hardcover

RRP $279.95

$242.75

13%OFF

or 4 interest-free payments of $60.69 with

or

Ships in 5 to 7 business days

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.

Industry Reviews

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

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

More in Mathematical Theory of Computation

AI Engineering

Building Applications with Foundation Models

Paperback

RRP $152.00

$73.75

51%
OFF

Algorithms in C, Parts 1-4

3rd Edition - Fundamentals, Data Structures, Sorting, Searching

Paperback

RRP $131.20

$81.75

38%
OFF

Swim Training Patterns : 1st Edition - Plan your Training Sessions with the Power of Mathematics - Christoph Bartneck

$117.75

Effective Machine Learning Teams

Best Practices for ML Practitioners

Paperback

RRP $152.00

$73.75

51%
OFF

Mathematics for Artificial Intelligence

Textbooks in Mathematics

Paperback

RRP $90.99

$82.75

Introduction to Modern Cryptography

Chapman & Hall/Crc Cryptography and Network Security

Hardcover

RRP $242.00

$233.75

Crypto Engine Design : Cyber Shorts - Wen-Long Chin

$73.75

51%
OFF

Introduction to Modern Cryptography : Revised Third Edition - Jonathan Katz

$73.75

51%
OFF

Hands-On Generative AI with Transformers and Diffusion Models

Paperback

RRP $152.00

$73.75

51%
OFF

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

Geometric Spanner Networks

At a Glance

Hardcover

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Mathematical Theory of Computation

AI Engineering

Building Applications with Foundation Models

Algorithms in C, Parts 1-4

3rd Edition - Fundamentals, Data Structures, Sorting, Searching

Swim Training Patterns

1st Edition - Plan your Training Sessions with the Power of Mathematics

Discrete Mathematics for Computing

Grassroots

Effective Machine Learning Teams

Best Practices for ML Practitioners

Mathematics for Artificial Intelligence

Textbooks in Mathematics

Introduction to Modern Cryptography

Chapman & Hall/Crc Cryptography and Network Security

Crypto Engine Design

Cyber Shorts

Exploring Complex Networks with Quantum Walks

Crypto Engine Design

Cyber Shorts

Machine Learning Interviews

Kickstart Your Machine Learning Career

Introduction to Modern Cryptography

Revised Third Edition

AI Value Creators

Beyond the Generative AI User Mindset

Hands-On Generative AI with Transformers and Diffusion Models

A Mathematical Introduction to Data Science with Python

Exploring Computational Geometry

Theory and Python Implementations

Risk Measures

An Introduction to the Mathematical Theory

Guide to Using Generative AI in Programming

Undergraduate Topics in Computer Science

Risk Measures

An Introduction to the Mathematical Theory

Quantum Computing

Foundations and Practice

BIM Geometry with Julia Plasmâ"Functional Language for CAD Programming

Volume 1: Mathematics and Software Engineering

Computer Vision

Cognitive Models for Visual Commonsense

Computability and Computational Explanation

Elements in the Philosophy of Mathematics

Computability and Computational Explanation

Elements in the Philosophy of Mathematics

This product is categorised by