Approximating Euclidean distances by small degree graphs

DOI10.1007/BF02574005zbMATH Open0790.51010MaRDI QIDQ1317879FDOQ1317879

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

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

zbMATH Keywords

approximating Euclidean distancesbounded degree spanners

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On sparse spanners of weighted graphs
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• Graph spanners
• Delaunay graphs are almost as good as complete graphs
• The Closest Packing of Spherical Caps in n Dimensions
• Classes of graphs which approximate the complete Euclidean graph
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Title not available (Why is that?)
• Generating sparse spanners for weighted graphs
• Title not available (Why is that?)

Cited In (11)

• \( \delta \)-greedy \(t\)-spanner
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

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)