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

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.