Almost all Delaunay Triangulations have Stretch Factor Greater than π/2

Let P be a set of points in the plane, and consider the Delaunay triangulation T of P. The spanning ratio of T is defined as the maximum dilation between any pair of points of P: 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 P such that T has a spanning ratio of more than 1.581, which is strictly larger than π/2, which is approximately 1.571. Furthermore, we show that any set of points drawn independently from the same distribution has high probability of also having a spanning ratio larger than π/2.


slides
keywords: Computational Geometry, Delaunay Triangulations

Journal Article (peer-reviewed)

Jack Snoeyink, Luc Devroye, Maarten Löffler, Prosenjit Bose, Vishal Verma
Almost all Delaunay Triangulations have Stretch Factor Greater than π/2
Computational Geometry: Theory and Applications
44, 2, 121–127, 2011
http://dx.doi.org/10.1016/j.comgeo.2010.09.009

Conference Proceedings (peer-reviewed)

Jack Snoeyink, Luc Devroye, Maarten Löffler, Prosenjit Bose, Vishal Verma
The spanning ratio of the Delaunay triangulation is greater than π/2
Proc. 21th Canadian Conference on Computational Geometry
165–167, 2009
Invited to Special Issue of CGTA

Archived Publication (not reviewed)

Jack Snoeyink, Luc Devroye, Maarten Löffler, Prosenjit Bose, Vishal Verma
The spanning ratio of the Delaunay triangulation is greater than π/2
1006.0291, 2010
http://arXiv.org/abs/1006.0291

back to list