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
shortest path; dilation; Delaunay triangulation; Euclidean distance; Euclidean graph; point configuration; stretch factor; point sets in convex position; spanning ratio
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
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