Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)

DOI10.1016/j.comgeo.2010.09.009zbMath1217.65044WikidataQ56970158 ScholiaQ56970158MaRDI QIDQ621930

Prosenjit Bose, Maarten Löffler, Vishal Verma, Jack Scott Snoeyink, Luc P. Devroye

Publication date: 31 January 2011

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.09.009

zbMATH Keywords

shortest path; dilation; Delaunay triangulation; Euclidean distance; Euclidean graph; point configuration; stretch factor; point sets in convex position; spanning ratio

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

05C12: Distance in graphs

52A37: Other problems of combinatorial convexity

52A10: Convex sets in (2) dimensions (including convex curves)

Related Items

IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION, Lower Bounds on the Dilation of Plane Spanners, Lower Bounds on the Dilation of Plane Spanners, Drawing graphs as spanners, Light Euclidean Spanners with Steiner Points, Improved routing on the Delaunay triangulation, On plane geometric spanners: a survey and open problems, On bounded degree plane strong geometric spanners, Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations, Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs, Constrained generalized Delaunay graphs are plane spanners, An exact algorithm for the minimum dilation triangulation problem, Upper and lower bounds for online routing on Delaunay triangulations, Emanation graph: a plane geometric spanner with Steiner points

Cites Work

• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• On the stretch factor of Delaunay triangulations of points in convex position
• Classes of graphs which approximate the complete Euclidean graph
• Differentiation of integrals in \(\mathbb{R}^n\)
• Structural tolerance and Delaunay triangulation
• There are planar graphs almost as good as the complete graph
• Competitive online routing in geometric graphs
• The geometric dilation of finite point sets
• Geometric Spanner Networks
• Approximating the Stretch Factor of Euclidean Graphs
• Finding the best shortcut in a geometric network
• On the Application of the Borel-Cantelli Lemma