Tight stretch factors for L1 L 1 - and L? L ? -Delaunay triangulations
In this paper we determine the exact stretch factor of L? L ? -Delaunay triangulations of points in the plane. We do this not only when the distance between the points is defined by the usual L2 L 2 -metric but also when it is defined by the Lp L p -metric, for any p?[1,?] p ? [ 1 , ? ] . We then apply this result to compute the exact stretch factor of L1 L 1 -Delaunay triangulations when the distance between the points is defined by the L1 L 1 -, L? L ? -, or L2 L 2 -metric. In the important case of the L2 L 2 -metric, we obtain that the stretch factor of L1 L 1 -Delaunay and L? L ? -Delaunay triangulations is exactly 4 + 2 2 ? 2.61 . This is the first time that the stretch factor of an Lp L p -Delaunay triangulation, for any p?[1,?] p ? [ 1 , ? ] , is determined exactly. We show, in particular, how to construct between any two points a and b  of an L1 L 1 -Delaunay or L? L ? -Delaunay triangulation a path whose length is no more than 4 + 2 2 times the Euclidean distance between a and b . This improves the bound of 10 by Chew (SoCG '86) [5]. We also describe families of point sets whose L1 L 1 -Delaunay or L? L ? -Delaunay triangulation has a stretch factor that can be made arbitrarily close to 4 + 2 2 .
stretch factor delaunay triangulation lp l p -metric lp l p lp l p l p geometric spanner