## 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.

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

### 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

back to list