The Delaunay triangulation closely approximates the complete Euclidean graph

DOI10.1007/3-540-51542-9_6MaRDI QIDQ4028874zbMATH OpenFDO

Authors J. Mark Keil, Carl A. Gutwin

Publication date 28 March 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-51542-9_6

zbMATH Keywords

complete graphDelaunay triangulationEuclidean distanceplanar graphshortest pathVoronoi diagram

Mathematics Subject Classification ID

Distance in graphs (05C12) Convex sets in (2) dimensions (including convex curves) (52A10) Other problems of combinatorial convexity (52A37)

Review text

[For the entire collection see Zbl 0753.00021.] Let \(S\) be a finite set of points in the plane. The Delaunay triangulation is the graph corresponding to the Voronoi diagram of \(S\). It is shown that for any two points of \(S\) the ratio between the length of the shortest path in the Delaunay triangulation and their Euclidean distance is less than 2.42.

Recommendations

• Delaunay graphs are almost as good as complete graphs
• Classes of graphs which approximate the complete Euclidean graph
• The stretch factor of the Delaunay triangulation is less than 1.998
• scientific article; zbMATH DE number 4070353
• scientific article; zbMATH DE number 4155926

Cited in

(19)

• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• The farthest point Delaunay triangulation minimizes angles
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• Beta-skeletons have unbounded dilation
• An exact algorithm for the minimum dilation triangulation problem
• Affine invariant triangulations
• scientific article; zbMATH DE number 4155926 (Why is no real title available?)
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• Dynamic proximity calculations for situation awareness
• Generating sparse spanners for weighted graphs
• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity
• Delaunay graphs are almost as good as complete graphs
• Improved stretch factor of Delaunay triangulations of points in convex position
• Self-stabilizing metric graphs
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• On the stretch factor of Delaunay triangulations of points in convex position
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Toughness and Delaunay triangulations
• Linear-size planar Manhattan network for convex point sets

This page was built for publication: The Delaunay triangulation closely approximates the complete Euclidean graph

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