Approximating Euclidean distances by small degree graphs
From MaRDI portal
Publication:1317879
DOI10.1007/BF02574005zbMath0790.51010MaRDI QIDQ1317879
Publication date: 26 June 1994
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131299
Related Items
\( \delta \)-greedy \(t\)-spanner ⋮ Euclidean spanner graphs with degree four ⋮ Computing the greedy spanner in near-quadratic time ⋮ An Optimal Dynamic Spanner for Doubling Metric Spaces ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Delaunay graphs are almost as good as complete graphs
- An O(n log n) algorithm for the all-nearest-neighbors problem
- Classes of graphs which approximate the complete Euclidean graph
- On sparse spanners of weighted graphs
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- Graph spanners
- Generating sparse spanners for weighted graphs
- The Closest Packing of Spherical Caps in n Dimensions