The Stretch Factor of L₁- and L_∞-Delaunay Triangulations

2012/02/23 by Bonichon, Nicolas, Gavoille, Cyril, Hanusse, Nicolas +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1202.5127

Abstract

In this paper we determine the stretch factor of the L₁-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 L_p-Delaunay triangulations, for any real p≥ 1, is determined exactly.

Related

• The Stretch Factor of Hexagon-Delaunay Triangulations
• Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation
• On the Stretch Factor of Convex Delaunay Graphs
• The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
• The dilation of the Delaunay triangulation is greater than \π/2