Dynamic algorithms for geometric spanners of small diameter: Randomized solutions

DOI10.1016/S0925-7721(99)00014-0MaRDI QIDQ1807649zbMATH OpenOpenAlexFDO

Authors Sunil Arya, David M. Mount, Michiel Smid

Publication date 7 March 2000

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0925-7721(99)00014-0, http://hdl.handle.net/11858/00-001M-0000-0014-B7A2-F

zbMATH Keywords

\(t\)-spanner path

Mathematics Subject Classification ID

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

Recommendations

• Fully dynamic geometric spanners
• Fully dynamic randomized algorithms for graph spanners
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Kinetic spanners in \(\mathbb{R}^d\)
• Kinetic spanners in \(\mathbb R^{d}\)

Cited in

(19)

• On the power of the semi-separated pair decomposition
• Temporal cliques admit sparse spanners
• A spanner for the day after
• Conic nearest neighbor queries and approximate Voronoi diagrams
• Matching point sets with respect to the earth mover's distance
• On the Power of the Semi-Separated Pair Decomposition
• Fully dynamic randomized algorithms for graph spanners
• Geometric Spanner of Objects under L 1 Distance
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• A spanner for the day after
• Temporal cliques admit sparse spanners
• A geometric spanner of segments
• Geometric Spanner of Segments
• Fully dynamic geometric spanners
• Ordered theta graphs
• Local routing algorithms on Euclidean spanners with small diameter
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees

This page was built for publication: Dynamic algorithms for geometric spanners of small diameter: Randomized solutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1807649)