PaperlayerView exact revision on arXiv

Source-linked AI summary

The Stretch Factor of Planar Delaunay Triangulations Is Less Than 1.65

Guanlin Mo, Kangke Cheng, Hu Ding

arXiv:2609.07979v3cs.CG

TL;DR

The paper addresses the open problem of bounding the worst-case stretch factor of planar Delaunay triangulations. It uses an additive Bellman formulation of disk chains and certifies an upper bound of 1.65, with a later extension reporting 1.5949.

  • Problem

    The smallest constant bounding shortest-path distances in Delaunay triangulations relative to Euclidean distance remains open, and several plane-spanner bounds depend on it.

    Source: §1 · p. 1

  • Method

    The proof compares ladder-path length with additive progress along the query line and uses a local potential whose geometric conditions reduce to a linear program over profiles.

    Source: §1.4 · pp. 3–4

  • Results

    The paper proves an upper bound of 1.65 for every planar Delaunay triangulation; a later extension reports 1.5949 and the interval [1.5932, 1.5949].

    Source: §8 · p. 30

  • Takeaways & Limitations

    The additive Bellman formulation makes the chain bound certifiable through local potential inequalities and a profile-based linear program.

    Source: §1.4 · pp. 3–4

    The theorem assumes a finite set of distinct planar points not all on one line and a specified straight-line Delaunay triangulation.

    Source: §3 · p. 6

Abstract

from arXiv · show

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 bound of \(1.998\) due to Xia (2011) and reducing the gap to the known lower bound of \(1.5932\) by a factor of more than seven. Our proof works with the chains of circumdisks introduced by Xia, along which a path between two sites is assembled disk by disk. Xia measures such a path against a quantity attached to the whole chain, and because that quantity is not additive, his induction has to be carried alongside a separate global estimate. Our main idea is to measure the path against the progress it makes along the segment joining the two sites. This quantity is additive, so the bound becomes a Bellman recursion that forgets all but one number about the disks already passed, and we show that the bound holds if and only if a potential on the current state satisfies three local inequalities. The smallest feasible potential is the value function of that recursion, so searching for a potential becomes the problem of fitting this value function from above. The geometry of the disks reduces the fit to a linear program over functions of one variable, in which a GPT-based multi-agent system that we developed found a feasible point, certified in exact arithmetic.

1 Introduction

The introduction reframes the Delaunay stretch-factor problem around an additive measure of progress along the query segment, yielding a Bellman approach to a 1.65 upper bound. It outlines the disk-chain reduction, the limits of the earlier global estimate, and the potential-based certification.

1 Introduction

  • The Delaunay stretch factor remains an open question, and improving its upper bound can also improve bounds for plane-spanner constructions that depend on it.The introduction places the result against earlier upper and lower bounds, including Xia’s bound below 1.998 and the known lower bound 1.5932.Source: §1 · pp. 1–2

1.1 Our Main Result

  • The proved upper bound of 1.65 narrows the known interval from [1.5932, 1.998] to [1.5932, 1.65].The theorem applies to a specified straight-line Delaunay triangulation, including cases with collinear subsets and cocircular groups of four or more sites.Source: §1.1 · p. 2

1.2 Chains of Circumdisks

  • Circumdisks crossed by the query segment form a chain whose rails and gates create a ladder path that bounds the Delaunay graph distance.Each rail can be replaced by Delaunay edges no longer than its arc, and each gate is itself a Delaunay edge.Source: §1.2 · p. 2, Figure 1 · p. 2

1.3 The Bottleneck in the Previous Analysis

  • Xia’s rubber-length measure is a global minimum rather than a sum of disk-by-disk contributions, requiring a separate global estimate alongside the induction.The combined analysis uses λ = 1.8 and yields a stretch bound of 1.998.Source: §1.3 · p. 3

1.4 Our Main Ideas

  • Comparing path cost with progress along the query line makes the reference quantity additive, enabling a Bellman recursion with a local potential.The bound follows from initialization, step, and termination inequalities; the Bellman value function is the smallest feasible potential.Source: §1.4 · p. 3

1.5 Contributions and Organization

  • The proof reduces the potential search to a linear program over a one-variable profile and certifies a feasible point at 1.65.The construction uses a cubic spline weight function and verifies the Bellman inequalities over all admissible states; the local state has four normalized parameters regardless of chain length.Source: §1.4 · p. 4, §1.5 · p. 4

2 Related Work

Prior work established constant upper bounds and the disk-chain framework for analyzing Delaunay stretch. This paper characterizes its chain bound through local potential inequalities and uses a function-space linear program to obtain a certified feasible bound.

Bounds on the Delaunay stretch factor

  • Xia reduced the upper bound below 1.998; the best published lower bound remains 1.5932, from Xia and Zhang.Earlier upper bounds include approximately 2.42 from Keil and Gutwin, while Chew established the lower bound π/2.Source: §2 · pp. 4–5

The disk-chain framework

  • Xia ’s disk-chain framework turns a Delaunay path question into bounding ladder paths through circumdisks crossed by the query segment.Rails and shared chords form the ladder, and a ladder path can be converted to a Delaunay path of no greater length.Source: §2 · p. 5

The paper’s analysis

  • Unlike Xia [22]’s rubber-length induction and global potential estimate, this paper uses an exact recursion whose chain bound is equivalent to three local potential inequalities.The Bellman value function is the pointwise smallest feasible potential; disk geometry then reduces sufficient conditions to a linear program over one-variable functions.Source: §2 · p. 5

Computer-assisted search and certification

  • The search approach is related to agent-assisted construction searches, formal verification, and prior searches for geometric bounds and potential functions.The authors identify the mathematical design of the search space and its reductions as the central content in this setting.Source: §2 · pp. 5–6
  • The authors’ reductions leave a linear program whose feasible point certifies a bound in exact arithmetic.Their certificate methods include rational Bernstein expansions for polynomial positivity and outward-directed interval arithmetic for transcendental conditions.Source: §2 · pp. 5–6

3 Preliminaries

The preliminaries define the Delaunay setting, the disk-chain ladder, and the local gate state used to analyze paths. They show how an additive query-line progress bound on chains yields a stretch bound for Delaunay graph distances.

3 Preliminaries

  • The setting fixes a specified straight-line Delaunay triangulation of a finite, non-collinear planar point set, with Euclidean edge lengths and induced shortest-path distance.Cocircular sites may admit multiple triangulations, and the specification fixes which one is considered.Source: §3 · p. 6

3.1 Chains of disks and the ladder

  • A disk chain’s rails and gates form a weighted ladder whose shortest terminal path bounds the corresponding Delaunay distance.Each gate is a shared chord between consecutive disks, and rails are the boundary arcs between incoming and outgoing caps; rails can be replaced by no-longer walks in the triangulation.Source: §3.1 · pp. 6–7

3.2 Chains crossed by a query line

  • For chains crossed by an oriented query line, progress along the ordered gate crossings adds to the Euclidean distance between the terminals.The chain class requires properly crossing consecutive circles, forward direction, and strictly ordered crossings.Source: §3.2 · p. 7

3.3 Gate states

  • A gate state records the current disk, its gate, and the difference between shortest prefix distances to the gate’s two tags.The ledger and balance summarize the prefix distances, while the state retains the balance separately from the ledger.Source: §3.3 · p. 8

3.4 Reduction to the chain bound

  • Bounding ladder paths by U times query-line progress for the chains generated by a segment suffices to bound Delaunay shortest paths by U times Euclidean distance.Rails can be replaced by Delaunay walks no longer than the rails, and subsegments split at sites on the query segment can be handled and concatenated.Source: §3.4 · pp. 8–9

4 The Bellman Form of the Chain Bound

The section reformulates the chain bound as additive accounting over gate states, using feasible potentials whose local inequalities telescope to a global bound. It also shows that admissible predecessors can be omitted from the state and sets up a normalized description of state shape.

4 The Bellman Form of the Chain Bound

  • The proof adds an initial condition, one step inequality per move, and a terminal condition, so the potential cancels and bounds ladder length by total progress.The accounting identity is along the ladder: it accumulates ladder length and query-line progress, with the potential absorbing their difference at each move.Source: §4 · p. 10, §4.2 · p. 15, Figure 3 · p. 15

4.1 An exact shortest-path recursion on the ladder

  • Properly crossing disks place forward and backward query points inside the respective outgoing and incoming caps; strongly disjoint caps delimit two rails on each disk.Source: §4.1 · pp. 10–11
  • The rails form a two-edge cut, so every simple source-to-target path uses exactly one rail per disk, yielding exact shortest-distance updates as the ladder grows.Source: §4.1 · p. 12
  • The recursion clips δ_i+α_i+1−β_i+1 to [−g_i+1, g_i+1] for the next balance and adds the corresponding increment j_i to ledger μ_i.Source: §4.1 · p. 14
  • For fixed rail and gate lengths, balance δ_i determines both the next balance and ledger increment, so the gate state stores δ_i while μ_i is kept separately.Source: §4.1 · p. 14
  • Initialization takes w−(O1) as an allowed source, while termination takes w+(O) as an allowed terminal and accounts for the final rails through κend.Source: §4.1 · p. 14

4.2 Three local inequalities

  • A feasible potential is finite, isometry-invariant, and degree-one homogeneous, and its local conditions must hold throughout the gate-state domain, including every δ∈[−g, g].Source: §4.2 · pp. 14–15
  • For U≥π/2, a feasible potential guarantees every chain in Q has PO(u, v)≤U∥u−v∥.Source: §4.2 · p. 15
  • For n = 2 the bound uses (I) and (T), while for n = 1 it follows from bound (3) and U ≥ π/2; the inequalities also hold at equality, including ties.Source: §4.2 · p. 15

4.3 Forgetting the predecessor

  • Admissible predecessors form a one-parameter family O(Y), and are exactly its members with Y < X, as the power-difference sign depends on X − Y and signed height above the gate line.Source: §4.3 · pp. 16–17
  • Every admissible predecessor cuts the same incoming cap from the current circle, while the forward and backward query points lie outside the respective disks.Source: §4.3 · p. 17
  • Because the cap and gate tags are unchanged, every admissible predecessor yields the same two rail lengths, and a termination is always available at the state.Source: §4.3 · p. 17
  • A feasible potential at level U ≥ π/2 implies bound (6) for every chain in Q; Section B proves the converse.Source: §4.3 · p. 17
  • Invariance and homogeneity allow normalization of the radius and query-line position, leaving state shape represented by four angles for a pointwise condition (E).Source: §4.3 · p. 17

5 Reduction to a Univariate Linear Program

This section reduces potential feasibility to pointwise conditions on a closed four-angle domain, then fixes the potential’s shape to formulate a univariate linear program over an even one-variable function. It gives a spline feasible point for the resulting sufficient conditions and uses the feasible potential to establish the stated bounds.

5.1 Normalized states and the closed angular domain

  • A normalized gate state is described by four angles, and checking inequalities on the closed angular domain suffices for all gate states.The closed domain also includes boundary configurations used as test cases.Source: §5.1 · pp. 17–18

5.2 Transport along a gate pencil

  • With the gate, query line, and balance fixed, disks form a one-parameter pencil; a nonincreasing potential along it controls the disk-change comparison.The pencil remains inside the strict domain over every closed finite interval of its parameter.Source: §5.2 · p. 18

5.3 The step residual

  • The step inequality follows from two comparisons: across the old circle and along the gate pencil, controlled by a nonpositive cleared step residual.The cleared residual is defined on the closed angular domain and is equivalent to the derivative residual at interior gate states.Source: §5.3 · pp. 19–21, Figure 5 · p. 20

5.4 Amplitude profiles and the sufficient conditions

  • Fixing the potential’s shape leaves an even one-variable amplitude profile, making the sufficient conditions affine in that function and its derivative.Theorem 5.7 states sufficient conditions under which the resulting potential is feasible at level U.Source: §5 · p. 17, §5.4 · pp. 22–23
  • The constructed W is a feasible potential at level U, yielding (6) by Theorem 4.7 and (32) by Proposition 3.3.The preceding verification applies the sufficient conditions to the transition, initialization, and termination cases.Source: §5.4 · pp. 23–24
  • At each fixed ε and point of C, the sufficient conditions are closed affine half-space constraints on the profile values and derivatives.The expression for E is affine in w and w′, and the other stated conditions are affine as well.Source: §5.4 · p. 24
  • A spline feasible point satisfies the semi-infinite linear program at U = 33/20.The program minimizes U over a one-variable function subject to constraints indexed by the compact set C.Source: §5.4 · p. 24

6 A Certified Spline Profile

The section reduces verification to finitely many branch and endpoint obligations, then exhibits a cubic spline feasible at 33/20 and certifies its conditions over their full closed domains.

6.1 Endpoint reduction and the two reflections

  • Eliminating the balance and applying two reflections reduces verification to three representative branch obligations with γ ≥ 0.The residual is affine in the balance, while the reflections halve the γ range and pair the six endpoint obligations.Source: §6.1 · p. 25

6.2 A spline profile and the main theorem

  • An even C2 cubic spline with exact rational coefficients is feasible at U = 33/20.The spline basis enforces consistency across γ, including matching conditions at its knots.Source: §6.2 · pp. 25–26

6.3 Certifying the closed conditions

  • Exact-arithmetic certification verifies the profile conditions and step-residual signs across the full closed domains.The proof uses rational Bernstein expansions for polynomial inequalities and exhaustive outward-directed interval covers for the remaining conditions.Source: §6.2 · p. 27, §6.3 · p. 28

6.2 A spline profile and the main theorem

  • The certified profile yields st(D) < 33/20 for every specified straight-line Delaunay triangulation covered by the theorem.The bound applies to every pair of sites, including when the point set has collinear subsets or cocircular groups.Source: §6.2 · pp. 26–27

7 The Agent-Assisted Search

The search fitted potential candidates to constraints derived from the geometric reductions, then certified a rational candidate exactly. A GPT-based multi-agent system proposed candidate shapes and guided the search.

7 The Agent-Assisted Search

  • The search fits a potential from above using a linear program over one-variable inequalities and pointwise constraints on C.The geometric reductions express the chain bound through local gate-state conditions and a pointwise condition on four angles.Source: §7 · p. 29
  • The system proposed candidate shapes, including a cubic spline replacing a quadratic amplitude, while the sufficient conditions remained fixed in advance.Theorem 5.7 applies to every ε in (0, 1] and every amplitude profile.Source: §7 · p. 29
  • 33/20 is certified by an exhaustive exact-arithmetic check that the rationalized candidate satisfies Theorem 5.7’s full hypotheses.The sampled spline optimum was near 1.633; the rational point had margin above it.Source: §7 · p. 29
  • Floating-point optimization guides candidate selection, but the proof depends on exact coefficients and verified inequalities, not the sampled optimum.The geometric reduction turns certification into a finite, checkable list of conditions.Source: §7 · p. 29

8 Conclusion and Further Improvements

The paper proves a 1.65 upper bound on the stretch factor of every planar Delaunay triangulation. It also reports a later improvement to 1.5949 using an extended potential, whose explicit form and certification are deferred.

8 Conclusion and Further Improvements

  • 1.65 is an upper bound on the stretch factor of every planar Delaunay triangulation, proved using a Bellman formulation and a univariate spline potential.Affine sufficient conditions in the profile and its derivative enable linear-program search and certification over the full continuous domain.Source: §8 · p. 30
  • 1.5949 is a further upper bound from an extended potential, narrowing the worst-case interval to [1.5932, 1.5949].The explicit potential and its certification are deferred to a later version.Source: §8 · p. 30

A From a Specified Delaunay Triangulation to Chains

The appendix supplies self-contained proofs of the geometric facts used to turn a specified Delaunay triangulation into circumdisk chains, using Xia’s framework. Its central construction groups faces into maximal cocircular cells whose boundary edges belong to the triangulation.

A From a Specified Delaunay Triangulation to Chains

  • The appendix proves five facts used in Section 3.4, including segment decomposition, ladder-path replacement, the one-disk bound, and membership of the resulting chains in Q.The proofs are included to make the paper self-contained within Xia’s framework.Source: A From a Specified Delaunay… · p. 30

A.1 Maximal cocircular cells

  • Each Delaunay face belongs to a unique maximal cocircular cell: an empty-circle convex polygon completely triangulated by the faces, with every boundary edge in D.The proof relates empty circumdisks to supporting planes of the lifted point set.Source: §A.1 · pp. 30–31
  • Every cell boundary edge belongs to D for every admissible triangulation of its cocircular polygon.Adjacent cell vertices have an open chord inside the empty disk, and no site subdivides that boundary edge.Source: §A.1 · p. 31

A.2 Decomposing a query segment

A query segment is decomposed into edges or ordered circumdisk chains, and each chain yields a triangulation walk no longer than its ladder path. For a one-disk chain, the shorter arc is bounded relative to its chord by the one-disk inequality.

A.2 Decomposing a query segment

  • Each positive-length segment between consecutive sites is either an edge of D or crosses an ordered disk chain with shared cell-boundary gates and the segment endpoints as terminals.The chain has strong cap-disjointness and terminal exposure.Source: §A.2 · p. 31

A.3 Expanding a ladder path in the triangulation

  • Replacing each rail of a shortest ladder path by the cell-boundary walk produces a walk in D of length at most the ladder path length.The boundary walk is no longer than its rail, including for major arcs and full-circle arcs.Source: §A.3 · p. 31

A.4 The one-disk bound

  • For a one-disk chain, the shorter arc length is at most π/2 times the chord length, with equality only for antipodal terminals.The ladder path is the shorter of the two complementary arcs.Source: §A.4 · p. 32

A.5 Coverage of the restricted class

The construction handles degeneracies and proves that the resulting disk chains belong to the restricted class Q. The proof verifies the class’s geometric and ordering conditions for each chain.

A.5 Coverage of the restricted class

  • The query segment crosses shared gates transversely and in strict order, with the terminals outside all interior crossings.The relative interior contains no site, and the query line cannot coincide with a gate’s supporting line.Source: §A.5 · p. 32
  • Chains from Lemma A.2 satisfy the crossing-direction condition: consecutive circumcircles cross properly, and their centers advance along the oriented query line.The proof establishes the direction using power differences, which change sign at each gate crossing.Source: §A.5 · p. 32
  • The caps are strongly disjoint, and the matching and rail-length conditions follow from Lemma 4.2, including zero-length rails.Together with the established crossing conditions, this verifies all conditions of Definition 3.1.Source: §A.5 · p. 32
  • Grouping cocircular faces into cells and splitting at interior sites handles degeneracies; positive-length overlaps are assigned to the actual-edge case.The resulting disk chains satisfy Q directly.Source: §A.5 · p. 32

B The Excess and Its Value Equation

The section characterizes the chain bound through the excess value function: the bound is equivalent to a feasible potential, and the excess is the smallest such potential. This gives the potential search a precise target: fitting the value function from above.

B The Excess and Its Value Equation

  • The excess is the supremum of continuation payoffs, each defined as remaining ladder cost minus U times remaining progress.The empty continuation ensures the supremum is over a nonempty set.Source: B The Excess and Its Value Equation · p. 33
  • For U ≥ π/2, the bound for every chain in Q holds if and only if a feasible potential at level U exists.The forward implication follows from Theorem 4.7; the converse is proved by bounding the excess.Source: B The Excess and Its Value Equation · p. 33
  • When the bound holds, the excess is finite at each gate state and balance, satisfies the value equation, and is the pointwise smallest feasible potential.Every feasible potential dominates it.Source: B The Excess and Its Value Equation · p. 33
  • To bound the excess, the proof places a predecessor disk and source before a state so each finite continuation becomes an actual chain in Q.The chain bound then supplies a finite upper bound independent of the continuation’s number, sizes, and disk geometry.Source: B The Excess and Its Value Equation · pp. 33–34
  • The equivalence makes potential construction a fit of the excess from above, with allowable slack governed by the initialization, step, and termination inequalities.The excess is a precise target for exhibiting a bound.Source: B The Excess and Its Value Equation · p. 34

C.1 The spline profile

The spline profile specifies a piecewise-polynomial fit and reports its endpoint values, including the bound at τ = 0.

C.1 The spline profile

  • The seven coefficients of (42) are given in decimal form, with λ_i B_i(τ) represented by polynomials on each closed knot interval in ascending powers of τ.Source: §C.1 · pp. 34–35
  • The base values are 39/200 = 0.195 and 28/125 = 0.224, with ε = 1/20; the condition λ0 = λ1 holds.Source: §C.1 · p. 35
  • At τ = 0, the value 39/200 + λ0 = 76579/500000 = 0.153158 gives the bound (44); at τ = 1, the value is 2.248723....The result retains the true factor (π/2)^2 through the quadratic base contribution.Source: §C.1 · p. 35

D Auxiliary Proofs

The auxiliary proofs support the construction and certification of the profile: they derive pencil identities, specify rigorous interval enclosures, and provide cover coordinates and residual forms. The branch conditions and boundary cases for the profile are verified by rigorous arithmetic certification.

D.1 The pencil identities

  • Differentiating the pencil geometry gives the identity used in Proposition 5.5, where terms carrying U cancel.The derivation uses x(o) = x(M) + X cos φ and substitutes the expression for A.Source: §D.1 · p. 35

D.2 The interval enclosures

  • Interval operations enclose true values by outward rounding; π, sine, and cosine are bounded using rational and Taylor approximations with remainders.The trigonometric enclosures also include exact extrema within the argument interval.Source: §D.2 · pp. 35–36

D.3 Cover coordinates and cancellation-free forms

  • Normalized arc coordinates map the closed diamond, including degenerate faces, into a unit cube and yield smooth expressions on the closed cube.The sinc bound ensures smoothness at t = 0; certifying an extension as nonpositive can be stronger than necessary on inaccessible branch faces.Source: §D.3 · p. 36
  • Cancellation-free coordinates rewrite the residuals, and the profile’s branch inequalities, switch gradients, and boundary cases are verified by rigorous arithmetic certification.At ψ = ±k, the last term vanishes; it is retained in the central interior.Source: §D.3 · pp. 36–37

D.4 The gate faces of the angular domain

Boundary identities are used to certify boxes touching faces of the angular domain. On both gate faces, the residual vanishes for every accessible incident gradient.

D.4 The gate faces of the angular domain

  • At φ=π/2, θ=π/2−γ and the stable interval is [k, π/2+cos γ]; H0=σ and J matches the term subtracted from γ in σ.The passage also states that (29) applies to this identity.Source: §D.4 · p. 37
  • At φ=−π/2, θ=π/2+γ and the stable interval is [−π/2−cos γ, −k]; the boundary computation makes the residual vanish on both gate faces.The computation differentiates along ψ=π/2+s cos γ, θ=π/2−γ and uses the incident-gradient switch condition.Source: §D.4 · p. 37
  • At γ=±π/2, eE=0; at θ=0 and θ=π, conditions (S) and (S′) dispose of the initialization and termination faces.On the latter faces, E equals the corresponding initialization or termination residual, and eE equals cos γ times it.Source: §D.4 · p. 37
  • A positive-volume box touching one of these faces is closed using the mean-value rules of Section 6.3.The cited face identities themselves hold on the faces.Source: §D.4 · p. 37
Loading 2609.07979v3…