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

DOI10.1016/j.comgeo.2010.09.009zbMath1217.65044OpenAlexW1993585122WikidataQ56970158 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 pathdilationDelaunay triangulationEuclidean distanceEuclidean graphpoint configurationstretch factorpoint sets in convex positionspanning ratio

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Distance in graphs (05C12) Other problems of combinatorial convexity (52A37) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items

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

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