A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane

1 Introduction

• The unresolved question was whether any o(n)-approximation exists, despite the MST's O(n) guarantee and the NP-hardness of exact construction.The hardness of approximation was not known to rule out a PTAS.Source: §1 · p. 2

1.1 Our contribution

• The first polynomial-time sublinear-approximation algorithm resolves the open question of whether the Euclidean-plane minimum dilation tree admits an o(n)-approximation.Its guarantee is O(n^14/15 log^3 n), with running time O(n^5 log n).Source: §1.1 · p. 2, §1 · p. 2
• The authors identify point-set structures that force dilation Ω(n^c), while their absence permits a minimum dilation tree with sublinear dilation.They describe these structural insights as potentially of independent interest.Source: §1.1 · p. 3

1.2 Other related work

• Related work studies relaxed variants including bounded-spread point sets, sparse spanners, tree covers, and minimum-dilation trees in unweighted graph metrics.These settings differ from the general Euclidean-plane minimum dilation tree problem addressed here.Source: §1.2 · p. 3

2 Warm-up

• The MST has dilation at most n−1, since a shortest tree path between a pair uses at most n−1 edges, each no longer than their direct distance.The path bound follows because otherwise the direct edge could replace a longer MST edge.Source: §2 · p. 4
• On two horizontal point rows, the MST has dilation at least n/8, while a comb has dilation 9.The two constructions demonstrate that the MST need not be the best tree for dilation.Source: §2 · p. 4
• Comb constructions have optimal dilation Ω(min(n/a, a)), while evenly spaced circle points force every tree to have dilation Ω(n).The circle lower bound also holds when adjacent-point distances are O(1/n).Source: §2 · p. 4
• Detecting generalized circle or comb obstructions guides the search for a tree-like structure that yields low dilation when those obstructions are absent.The approach checks whether such obstructions occur in any subset of the points.Source: §2 · p. 4

3 Preliminaries

• A graph's dilation is the maximum, over point pairs, of shortest-path distance in the graph divided by their Euclidean distance; the minimum dilation tree minimizes this value over spanning trees.The graph uses Euclidean edge lengths.Source: §3 · p. 5
• The r-support comprises polygons formed by the outer edges of Delaunay components after removing edges longer than r.The support captures point-set shape at scale r; Figure 2 illustrates two weakly simple polygons.Source: §3 · p. 5, Figure 2 · p. 6
• For a fixed point set, fewer than 3n distinct r-supports occur across all choices of r.Source: §3 · p. 5
• A point set is Λ-thin when every polygon in each r-support contains no disk of radius greater than Λr.A polygon is Λ-thin when its largest contained disk has radius at most Λ.Source: §3 · p. 5

• A certificate that Opt ≥ Λ lets the MST’s dilation n−1 yield an n/Λ approximation to the minimum dilation tree.Source: §4 · p. 6
• If the point set is not Λ-thin, Opt is Ω(Λ); if it is Λ-thin, a cross-scale comb-like structure can certify the same lower bound.Source: §4 · p. 6
• For Λ-thin sets, the algorithm tests nested forest-like polygons at scales r0, Λr0, Λ^2r0, … for consistency across scales.For super-quadratic spread, the sequence is compressed to at most n^2 values of Λ^k.Source: §4 · p. 6
• At each scale, the construction connects prior-scale trees within each r-support component, using edges of length at most Λ^2r and separating components for edges of that length.It targets pairs at Euclidean distance in [r/Λ, r].Source: §4 · p. 6
• Cuts derived from the next-scale support limit which pairs a scale handles, leaving cross-piece pairs to later scales and preventing cuts from propagating through earlier components.Figure 3 illustrates the cut through the orange r-support and the blue edges added at the next scale.Source: §4 · pp. 6–7, Figure 3 · p. 7
• O(max{n/Λ, Λ^k}) bounds the computed tree’s dilation; choosing Λ=n^c with c=1/(k+1) minimizes this bound.Since Opt ≥ 1, this also bounds the approximation ratio.Source: §4 · p. 7

5.1 Circle obstructions

• Opt ≥ 2R/r when a weakly simple polygon in the r-support contains a disk of radius R; Λ-thinness is testable in O(n^2) time, and failure implies Opt ≥ 2Λ.The algorithm checks the distinct r-supports for polygons that contain a disk of radius Λr.Source: §5.1 · pp. 8–9

5.2 Converting a Λ-thin polygon into a tree

• A Λ-thin point set admits an O(n log n)-time, 1/12-distance-preserving (12Λr)-tree partition for each weakly simple polygon in its r-support.The partition's pieces have geodesic diameter at most 12Λr, and ancestor-descendant tree distance preserves polygon distance up to the stated factor.Source: §5.2 · pp. 10–11
• For Λ ≥ 3, an O(n log n)-time construction yields a (12Λr, 2/3Λ^2r, 24Λ^2r log n)-junction tree from the tree partition.Junctions are separated checkpoints, while faces group the unmarked pieces of a heavy-light decomposition.Source: §5.2 · pp. 11–12

5.3 Comb obstructions

• A disconnected spine-cutting graph in a junction-tree face yields a comb obstruction and a lower bound Opt ∈ Ω(Λ).Spines and nerves are connected components of the (Λ−1)r- and (Λ−2)r-supports within a face.Source: §5.3 · p. 13
• For each nerve Ni,j, the tree path Li,j between points near adjacent junctions stays within ηr/(2Λ) of nerve vertices and inside P.The points are chosen so a path within the nerve between them has edges of length at most r/Λ^2.Source: §5.3 · p. 14
• Pairwise vertex-disjoint paths are joined cyclically into a closed walk; balancing edge traversals forces a long connector between points near one junction, contradicting the dilation bound.The connector is long by the pigeonhole principle, but the junction’s bounded geodesic diameter and the assumed dilation give it a shorter upper bound.Source: §5.3 · p. 15
• Every spanning tree of S has dilation at least 1/(27Λ).Source: §5.3 · p. 15

6 Structuring the point set via the spine-cutting graph

• The construction focuses on Λ-thin point sets with connected spine-cutting graphs, using minimal realizations and selected scales as the bottom-up algorithm’s backbone.The cuts are chosen in P_{Λ−1}^r and depend only on P_r.Source: §6 · p. 15

6.1 Realizing the spine-cutting graph

• A minimal realization C avoids F-nerves, lies in qualifying spines, connects the induced spine-cutting graph, and leaves every component of a cut spine touching a junction.A well-spaced realization additionally requires the point graph within each remaining component, using edges of geodesic length at most 3r, to be connected.Source: §6.1 · p. 16
• The algorithm builds an auxiliary graph whose paths represent routes through spines avoiding nerves, then embeds a connecting forest as a cycle-free planar straight-line graph.The embedding places vertices at crossed triangulation-edge midpoints and connects them within traversed triangles.Source: §6.1 · p. 17
• The resulting realization is well-spaced, and a straightforward implementation takes O(n^2 log n) time.Its construction also ensures that it avoids F-nerves and that every component left in a spine intersects a junction.Source: §6.1 · p. 17

6.2 A consistent sequence of junction trees

• The compressed scale sequence has O(n^2) relevant values, with successive ratios either Λ or greater than Λ^10, and brackets every pairwise point distance at a scale ratio of Λ.This sequence avoids dependence on a potentially superpolynomial range of scales.Source: §6.2 · p. 18
• A sequence of junction trees is consistent when every face has a connected spine-cutting graph; the paper computes one in O(n^5 log n) time or certifies the stated lower bound on Opt.The construction considers O(n^2) scales and builds junction trees and tests face connectivity at each scale.Source: §6.2 · p. 18

7 The algorithm

• The algorithm achieves an ˜O(n^14/15)-approximation for the minimum dilation tree on any point set in R^2.For a consistent compressed scale sequence, it constructs a tree with dilation O(max{n/Λ, Λ^14}).Source: §7 · p. 18

7.1 Description of the algorithm

• With Λ≥5, the algorithm checks lower-bound cases and returns the minimum spanning tree when certified; otherwise, it runs the two scale sweeps.The scale-separation factor is later set to approximately n^1/15.Source: §7.1 · pp. 18–19
• The algorithm first sweeps scales coarse to fine to construct cuts, then sweeps fine to coarse to build the tree within the resulting subpolygons.At the final largest scale, the subpolygon contains all points, so the output is connected.Source: §7.1 · pp. 19–20

7.2 Correctness

• The correctness invariants bound junction-star edges by 18Λr and face-star edges by 27(Λ^2 log n)r, and constrain relevant tree paths to a local ball.For the stated same-subpolygon point pairs, the path lies within B_Pr(p, (102 log n + 6)Λ^2r).Source: §7.2 · pp. 21–23
• For points in the same subpolygon at Euclidean distance at most r, the dilation is at most 209 034 929 709 log^3 n max(n/Λ, Λ^14).The invariants hold under the condition Λ≥5 and imply that the terminating graph is a tree on S with bounded dilation.Source: §7.2 · p. 21
• For same-subpolygon pairs at distance in [Λ^-2r, r], dilation is at most δ^2(17 917 056 + 4 320 log n)Λ^14 + (18 + 27 log n)n.The proof uses locality to confine the path to a ball, then bounds the number and lengths of intersecting junction- and face-stars across scales.Source: §7.2 · pp. 25, 27

7.3 Putting everything together

• O(n^14/15 log^3 n) approximation for minimum dilation trees is achieved in O(n^5 log n) time.The running time is dominated by constructing the consistent sequence.Source: §7.3 · p. 27
• O(min{∆, n^14/15 log^3 n}) approximation is available for point sets with spread ∆, in polynomial time.The algorithm returns the lower-dilation tree between the Theorem 1 tree and a star centered at an arbitrary point.Source: §7.3 · p. 27

8 Conclusion

• The algorithm breaks the Ω(n) approximability barrier for minimum dilation trees on arbitrary point sets in R2, resolving a long-standing open question.The paper also categorizes point sets whose dilation is at least Ω(n^14/15 log^3 n).Source: §8 · p. 27
• The O(n^5) running-time bound is pessimistic, and the authors consider pushing the overall running time below ~n^3 plausible, though optimization was not the focus.They note that the compressed scale sequence can be reduced to O(n) and the spine-cutting graph computed in sub-cubic time.Source: §8 · pp. 27–28
• The stated approximation ratio is unlikely to be tight; the authors identify O(n^14/15 log^1/5 n) as an achievable improvement and an O(√n) barrier for their approach.Getting close to or breaking that barrier will likely require novel insights and techniques.Source: §8 · p. 28
• The algorithm is far from practical because its large constant makes its guarantee better than the minimum spanning tree only for n ≥ 21000.The stated constant is 209 034 929 709.Source: §8 · p. 28
• Whether the techniques extend to higher dimensions or doubling spaces remains open.The r-tree-dissection appears to require a stronger structural result than a three-dimensional version of the circle obstruction.Source: §8 · p. 28