An Optimal Dynamic Spanner for Doubling Metric Spaces
From MaRDI portal
Publication:3541109
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
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