Minimum dilation tree approximation problem

Given a finite point set $P\subset\mathbb{R}^2$ with $|P|=n$ , let $T$ range over spanning trees on $P$ , with each edge weighted by its Euclidean length. Define the dilation of $T$ by $\delta(T)=\max_{p\ne q\in P}\frac{d_T(p,q)}{\lVert p-q\rVert_2}$ , where $d_T$ is the shortest-path distance in $T$ , and let $\operatorname{OPT}(P)=\min_T\delta(T)$ . Does there exist a constant $\varepsilon>0$ and a polynomial-time algorithm that, for every such $P$ , outputs a spanning tree $T$ satisfying $\delta(T)\le O(n^{1-\varepsilon})\operatorname{OPT}(P)$ ?

References

Primary source

arXiv

Additional references

A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane — arXiv

Posted 4 weeks ago

Progress summary

Refreshed 4 weeks ago

Claimed progress

A new paper claims the first general improvement over the linear approximation guarantee, but the result has not been independently verified.

The problem asks for an approximation to the minimum-dilation tree problem, posed as an open question by Eppstein. Before this development, the best general guarantee was linear in the number of points.

Known results

The minimum spanning tree gives an $O(n)$ approximation; no $o(n)$ guarantee was known (2007).
The exact Euclidean decision problem is $\mathrm{NP}$ -hard for planar point sets (2007).
In 2024, the approximation question was explicitly restated as open, including whether an $O(n^{1-\varepsilon})$ approximation exists for some $\varepsilon>0$ .

September 8, 2026 claimed sublinear approximation

A paper titled A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane claims the first asymptotically sublinear general-purpose approximation for planar Euclidean point sets. The claim is reported but not independently verified; hardness and near-optimality remain unsettled.

Current status (as of September 2026): The linear baseline and prior hardness results are established, while a claimed sublinear planar approximation is new and remains unverified.

Sources

No solutions have been posted yet.