Fully dynamic geometric spanners

DOI10.1007/s00453-011-9504-7zbMath1236.68281MaRDI QIDQ5920251

Liam Roditty

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9504-7

zbMATH Keywords

geometric spanners; \(t\)-spanner

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

The Greedy Spanner Is Existentially Optimal, Geodesic Spanners for Points on a Polyhedral Terrain, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Incremental algorithm for maintaining a DFS tree for undirected graphs, On Locality-Sensitive Orderings and Their Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Ordered theta graphs
• Biased skip lists
• 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
• Deformable spanners and applications
• Searching dynamic point sets in spaces with bounded doubling dimension
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• The skip quadtree
• Dynamic Algorithms for Graph Spanners
• Algorithms – ESA 2005
• A simple and efficient kinetic spanner