Most finite point sets in the plane have dilation \(>1\) (Q2256585)

Let \(S\) be a finite point set in the plane. Consider a geometric graph \(T=(V,E)\) drawn in the plane, such that its vertex set contains \(S\). The dilation of a pair of vertices in \(T\) is the minimum sum of lengths of edges along paths connecting them in \(T\) divided by the Euclidean distance of the pair of vertices. The dilation of \(T\) is the maximum dilation of a pair of vertices. David Eppstein characterized triangulations with dilation 1. Call a point set \(S\) special, if it is contained as a subset of the vertex set of some of Eppstein's triangulations. The main result of the paper states that if a finite point set \(S\) is not special, then there exists a \(\Delta(S)>1\) number, such that for any geometric graph \(T=(V,E)\) drawn in the plane, such that its vertex set contains \(S\), the dilation of the graph \(T\) exceeds \(\Delta(S)\).