Euclidean minimum spanning trees in three and more dimensions

Connecting $n$ points in the plane by the shortest possible network of straight segments takes $O(n\log n)$ time. In three dimensions the best algorithms still need about $n^{4/3}$ time, and in high dimensions close to $n^2$. Can the Euclidean minimum spanning tree be computed in near-linear time in every fixed dimension?

Problem

Let $P$ be a set of $n$ points in $\mathbb{R}^d$. The Euclidean minimum spanning tree (EMST) of $P$ is a spanning tree of the complete graph on $P$ whose total edge length, measured in the Euclidean norm, is as small as possible.

Question. For fixed $d\ge 3$, can the EMST be computed in time close to the lower bound of $\Omega(n\log n)$, for example in $O(n\log n)$ or $n^{1+o(1)}$ time?

Background

In the plane the EMST is a subgraph of the Delaunay triangulation, which has $O(n)$ edges, so it can be found in $O(n\log n)$ time. In higher dimensions the Delaunay triangulation can be the complete graph, and this approach fails. General graph algorithms do not help either, because the complete geometric graph has $\Theta(n^2)$ edges. The problem is Problem 5 of The Open Problems Project, in its original list of thirty, and it is closely tied to bichromatic closest pairs, a basic primitive of geometric algorithms.

What is known

• Lower bound. $\Omega(n\log n)$ time is needed even with randomized algebraic decision trees (Grigoriev, Karpinski, Meyer auf der Heide and Smolensky, 1996).
• Reduction to closest pairs. Agarwal, Edelsbrunner, Schwarzkopf and Welzl (1991) showed that computing the EMST is equivalent, up to polylogarithmic factors, to finding the closest pair between a red and a blue point set. This gave expected time $O((n\log n)^{4/3})$ for $d=3$ and deterministic time $O(n^{2-2/(\lceil d/2\rceil+1)+\varepsilon})$ for any fixed $d$ [1].
• Current record in 3D and 4D. Chan and Zheng (2022) gave randomized $O(n^{4/3})$-time algorithms for the bichromatic closest pair and the EMST in three and four dimensions [3].
• Approximation is easy. For every fixed $\varepsilon>0$, a spanning tree within a factor $1+\varepsilon$ of the minimum can be found in $O(n\log n)$ time with Callahan's well-separated pair decomposition [2], [4].

What would count as progress

• An algorithm computing the EMST in $\mathbb{R}^3$ in $o(n^{4/3})$ time, with a proof of its running time. An implementation can be checked against Prim's algorithm on the complete graph, which takes $O(n^2)$ time.
• A faster algorithm for the bichromatic closest pair problem in $\mathbb{R}^3$, which by the reduction gives one for the EMST.
• A lower bound of the form $\Omega(n^{4/3})$ for EMST in $\mathbb{R}^3$ in a natural restricted model, or a conditional lower bound from a standard hypothesis.

References

1. P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf and E. Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete Comput. Geom. 6 (1991), 407–422. doi:10.1007/BF02574698
2. P. B. Callahan and S. R. Kosaraju, A decomposition of multidimensional point sets with applications to $k$-nearest-neighbors and $n$-body potential fields, J. ACM 42 (1995), 67–90. doi:10.1145/200836.200853
3. T. M. Chan and D. W. Zheng, Hopcroft's problem, log-star shaving, 2D fractional cascading, and decision trees, Proc. SODA 2022; ACM Trans. Algorithms 20 (2024). doi:10.1145/3591357, arXiv:2111.03744
4. D. Eppstein, Spanning trees and spanners, in Handbook of Computational Geometry, Elsevier (2000), 425–461. doi:10.1016/B978-044482537-7/50010-3, preprint

Source

Imported from The Open Problems Project, Problem 5, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.