scientific article; zbMATH DE number 140458

zbMATH Open0766.52004MaRDI QIDQ4028874FDOQ4028874

Authors: J. Mark Keil, Carl A. Gutwin 

Publication date: 28 March 1993

Title of this publication is not available (Why is that?)

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

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)

Cited In (19)

• Linear-size planar Manhattan network for convex point sets
• 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
• Title not available (Why is that?)
• 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
• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity
• Title not available (Why is that?)

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)