Delaunay triangulations guaranteed to stretch paths by less than 1.65 times
The Stretch Factor of Planar Delaunay Triangulations Is Less Than 1.65
Computational Geometry
Summary
When connecting points in a plane with triangles, some connections make routes longer than the straight distance. The authors improved the known maximum factor by which these routes can stretch, proving it's less than 1.65 times the direct distance. They used a new approach involving a mathematical tool called a Bellman formulation to track progress along the route precisely. This means paths through these triangles are closer to the shortest possible than previously proven.
What this means in practice
- •For network designers: Design and analyze wireless sensor networks ensuring efficient routing with path lengths close to direct distances using planar Delaunay triangulations.
- •For geographic information system developers: Optimize map-based route planning by leveraging improved stretch factor bounds in triangulated spatial graphs for more accurate path estimates.
A theory result. No direct application yet.
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.