Tight stretch factors for L1L1- 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 L2L2-metric but also when it is defined by the LpLp-metric, for any p∈[1,∞]p∈[1,∞]. We then apply this result to compute the exact stretch factor of L1L1-Delaunay triangulations when the distance between the points is defined by the L1L1-, L∞L∞-, or L2L2-metric.In the important case of the L2L2-metric, we obtain that the stretch factor of L1L1-Delaunay and L∞L∞-Delaunay triangulations is exactly 4+22≈2.61. This is the first time that the stretch factor of an LpLp-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 L1L1-Delaunay or L∞L∞-Delaunay triangulation a path whose length is no more than 4+22 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 L1L1-Delaunay or L∞L∞-Delaunay triangulation has a stretch factor that can be made arbitrarily close to 4+22.