The spanning ratio of the delaunay triangulation is greater than =2
Consider the Delaunay triangulation T of a set P of points in the plane. The spanning ratio of T, i.e. the maximum ratio between the length of the shortest path between this pair on the graph of the triangulation and their Euclidean distance. It has long been conjectured that the spanning ratio of T can be at most =2. We show in this note that there exist point sets in convex position with a spanning ratio > 1:5810 and in general position with a spanning ratio > 1:5846, both of which are strictly larger than =2 , 1:5708. Furthermore, we show that any set of points drawn independently from the same distribution will, with high probability, have a spanning ratio larger than π/2.
|Conference||21st Annual Canadian Conference on Computational Geometry, CCCG 2009|
Bose, P, Devroye, L. (Luc), Löpffler, M. (Maarten), Snoeyink, J. (Jack), & Verma, V. (Vishal). (2009). The spanning ratio of the delaunay triangulation is greater than =2. Presented at the 21st Annual Canadian Conference on Computational Geometry, CCCG 2009.