scientific article; zbMATH DE number 140458

MaRDI QIDQ4028874zbMATH OpenFDO

Authors J. Mark Keil, Carl A. Gutwin

Publication date 28 March 1993

zbMATH Keywords

shortest pathDelaunay triangulationplanar graphVoronoi diagramcomplete graphEuclidean distance

Mathematics Subject Classification ID

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

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)

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

This page was built for publication:

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