An Optimal Dynamic Spanner for Doubling Metric Spaces

DOI10.1007/978-3-540-87744-8_40zbMath1158.68431MaRDI QIDQ3541109

Liam Roditty, Lee-Ad J. Gottlieb

Publication date: 25 November 2008

Published in: Algorithms - ESA 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87744-8_40

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

The Greedy Spanner Is Existentially Optimal, Unnamed Item, On Locality-Sensitive Orderings and Their Applications, Truly Optimal Euclidean Spanners, Geodesic Spanners for Points on a Polyhedral Terrain, Near Isometric Terminal Embeddings for Doubling Metrics, A simple and efficient kinetic spanner, Fully dynamic geometric spanners, Vertex Fault-Tolerant Geometric Spanners for Weighted Points, Kinetic spanners in \(\mathbb R^{d}\), Geometric spanners for weighted point sets, Approximation algorithm for the kinetic robust \(k\)-center problem, Fractal dimension and lower bounds for geometric problems, Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes, Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree, Linear-size approximations to the Vietoris-Rips filtration, Near isometric terminal embeddings for doubling metrics, The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme, New Doubling Spanners: Better and Simpler, On Locality-Sensitive Orderings and Their Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Ordered theta graphs
• Approximating Euclidean distances by small degree graphs
• Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• Searching dynamic point sets in spaces with bounded doubling dimension
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Deformable spanners and applications
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Fully dynamic geometric spanners