The Stretch Factor of L1- and L∞-Delaunay Triangulations

In this paper we determine the stretch factor of the L1-Delaunay and L∞-Delaunay triangulations, and we show that this stretch is 4 + 2 2 ≈ 2.61. Between any two points x, y of such triangulations, we construct a path whose length is no more than√ 4 + 2 2 times the Euclidean distance between x and y, and this bound is best possible. This definitively improves the 25-year old bound of 10 by Chew (SoCG ’86). To the best of our knowledge, this is the first time the stretch factor of the well-studied Lp-Delaunay triangulations, for any real p ≥ 1, is determined exactly