An Optimal Dynamic Spanner for Doubling Metric Spaces

DOI10.1007/978-3-540-87744-8_40zbMath1158.68431OpenAlexW1769399376MaRDI 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

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

Related Items (21)

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

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

This page was built for publication: An Optimal Dynamic Spanner for Doubling Metric Spaces