Euclidean Minimum Spanning Tree

Definitions and mathematical statement

Fix an integer $d\ge2$. For an input set $S=\{p_1,\ldots,p_n\}\subset \mathbb R^d$, give the complete graph on $S$ the edge weight $w(ij)=\|p_i-p_j\|_2$. A spanning tree is a connected acyclic graph on all $n$ vertices. A Euclidean minimum spanning tree is a spanning tree minimizing \[ \sum_{ij\in E(T)}\|p_i-p_j\|_2. \] The output is its set of $n-1$ edges; if several trees are optimal, any one is acceptable.

Can an exact Euclidean minimum spanning tree be computed, in every fixed dimension, in time close to $n\log n$? An $O(n\log n)$ algorithm would match the comparison-model benchmark; an $n\log^{O(1)}n$ algorithm is the weaker near-linear target. Constants may depend on $d$, so the dimension is not part of the growing input.

Use the usual real-arithmetic geometric model, in which coordinates and comparisons of squared distances can be processed exactly at unit cost. The complete graph is specified implicitly by its points: explicitly listing all its quadratic number of edges defeats the target. The request concerns exact optimality, not a $(1+\varepsilon)$ approximation.

Short English statement

Can the exact Euclidean minimum spanning tree be found in nearly $n\log n$ time in every fixed dimension, without generating all pairwise distances?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500005 (AMR-054-0005), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 5. Original source indexed by AMR-054-0005. https://topp.openproblem.net/p5.