An exclusion region for minimum dilation triangulations.
Christian Knauer, Wolfgang Mulzer · 2005
Given a planar graph G ,t hegraph theoretic dilation of G is defined as the maximum ratio of the shortestpath distance and the Euclidean distance between any two vertices of G. Given a planar point set S, a triangulation of S that achieves minimum graph theoretic dilation is called a minimum dilation triangulation of S. In this paper, we show that a simple exclusion region for an edge e of the minimum dilation triangulation is given by the disk of radius α|e| centered at the midpoint of e, where α is any constant < 3c os(π/6)/(4π) ≈ 0.2067.