Approximating Euclidean distances by small degree graphs

DOI10.1007/BF02574005MaRDI QIDQ1317879zbMATH OpenFDO

Authors 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)

Recommendations

• Euclidean spanner graphs with degree four
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Efficient construction of a bounded-degree spanner with low weight
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• There are plane spanners of degree 4 and moderate stretch factor

Cites work

• scientific article; zbMATH DE number 4155926 (Why is no real title available?)
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 192896 (Why is no real title available?)
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Classes of graphs which approximate the complete Euclidean graph
• Delaunay graphs are almost as good as complete graphs
• Generating sparse spanners for weighted graphs
• Graph spanners
• On sparse spanners of weighted graphs
• The Closest Packing of Spherical Caps in n Dimensions

Cited in

(11)

• \( \delta \)-greedy \(t\)-spanner
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 910877 (Why is no real title available?)
• Computing the greedy spanner in near-quadratic time
• Spanners under the Hausdorff and Fréchet distances
• Spanners in randomly weighted graphs: Euclidean case
• On the relation between graph distance and Euclidean distance in random geometric graphs
• Euclidean spanner graphs with degree four
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Euclidean spanners in high dimensions
• The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension

This page was built for publication: Approximating Euclidean distances by small degree graphs

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