Planar Delaunay triangulations have a stretch factor under 1.65
The Stretch Factor of Planar Delaunay Triangulations Is Less Than 1.65
Computational Geometry
Summary
The paper deals with Delaunay triangulations, which are ways to connect points on a plane with triangles without overlaps. One important question is how much longer paths between points can get when following these triangles compared to straight lines, called the stretch factor. The authors improved the known maximum stretch factor from about 2.0 to less than 1.65, getting closer to the theoretical minimum of about 1.59. They used a mathematical method called a Bellman formulation and a careful construction to prove this new upper bound. This work helps us better understand how efficient these triangulations are for problems like network design and geographic routing.
Delaunay triangulationstretch factorplanar graphplane spannercomputational geometryBellman formulationshortest pathdisk-chainpotential functioninterval arithmetic
Authors
Guanlin Mo, Kangke Cheng, Hu Ding
Abstract
Delaunay triangulations are a fundamental class of plane spanners, and determining their worst-case stretch factor has been a longstanding problem in computational geometry. We prove an upper bound of 1.65, improving the previous bound of 1.998 and reducing the gap to the known lower bound of 1.5932 by a factor of more than seven. The result holds for every planar Delaunay triangulation, including configurations with collinear or cocircular sites. Our main contribution is a Bellman formulation of the disk-chain bound underlying the proof. By comparing shortest-path length with additive progress along the query segment, we obtain an exact recursion whose state records only the current disk, the incoming chord, and the difference between two prefix distances. We show that a bound for this chain class holds if and only if a potential satisfies three local inequalities for initialization, transitions, and termination. The associated Bellman value function is the pointwise smallest feasible potential, giving a precise target for constructing an upper bound. We construct such a potential using a function of one variable. Geometric monotonicity reduces its feasibility to inequalities that are affine in this function and its derivative. A spline construction, certified by exact arithmetic and rigorous interval bounds, yields the stretch bound of 1.65. We also give a dual certificate showing that every feasible quadratic profile under the same conditions requires a certified constant greater than 1.67.