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

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
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
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
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.