Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
From MaRDI portal
Publication:3149878
DOI10.1137/S0097539700382947zbMath1041.68108OpenAlexW2004476837MaRDI QIDQ3149878
Giri Narasimhan, Joachim Gudmundsson, Christos Levcopoulos
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539700382947
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items (27)
\( \delta \)-greedy \(t\)-spanner ⋮ Euclidean Steiner Spanners: Light and Sparse ⋮ A GEOMETRIC SPANNER OF SEGMENTS ⋮ EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER ⋮ Truly Optimal Euclidean Spanners ⋮ On plane geometric spanners: a survey and open problems ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ On the stretch factor of Delaunay triangulations of points in convex position ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Geometric Spanner of Objects under L 1 Distance ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ On dynamic shortest paths problems ⋮ On certain geometric properties of the Yao-Yao graphs ⋮ Computing the greedy spanner in near-quadratic time ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Constructing minimum-interference networks ⋮ A spanner for the day after ⋮ Geometric Spanner of Segments ⋮ A simple and efficient kinetic spanner ⋮ Stable roommates spanner ⋮ Improved local algorithms for spanner construction ⋮ Unnamed Item ⋮ Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies ⋮ The Minimal Manhattan Network Problem in Three Dimensions ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ The Greedy Spanner Is Existentially Optimal ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
This page was built for publication: Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
