Approximating Euclidean distances by small degree graphs

DOI10.1007/BF02574005zbMath0790.51010MaRDI QIDQ1317879

V. Pereyra

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

zbMATH Keywords

approximating Euclidean distancesbounded degree spanners

Mathematics Subject Classification ID

Distance in graphs (05C12) General theory of distance geometry (51K05)

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