Toward the tight bound of the stretch factor of Delaunay triangulations
Ge Xia, Liang Zhang · 2011
In this paper, we investigate the tight bound of the stretch factor of the Delaunay triangulation by studying the stretch factor of the chain (Xia 2011). We define a sequence Γ = (Γ1,Γ2,Γ3,...) where Γi is the maximum stretch factor of a chain of i circles, and show that Γ is strictly increasing. We then present an improved lower bound of 1.5932 for the stretch factors of the Delaunay triangulation. This bound is derived from a sequence of chains sharing a set of properties. We conjecture that these properties are also shared by a chain with the worst stretch factor.