**Next:** Problem 6: Minimum Euclidean Matching in 2D

**Previous:** Problem 4: Union of Fat Objects in 3D

- Statement
Can the Euclidean

*minimum spanning tree*(MST) of n points in \R^d be computed in time close to the lower bound of \Omega(n \log n) [GKFS96]?- Origin
Uncertain, pending investigation.

- Status/Conjectures
Open.

- Partial and Related Results
Several algorithms have been developed for general graphs with arbitrary edge weights. Chazelle presented an O(m \alpha(m,n) \log \alpha(m,n))-time algorithm [Cha97], and then an O(m \alpha(m,n))-time algorithm [Cha00b], where \alpha(m,n) is the functional inverse of Ackermann’s function, and n and m are the number of vertices and edges respectively in the graph. Pettie and Ramachandran have since given an optimal algorithm for the graph setting [PR02], whose running time is an unknown function between \Omega(m) and O(m \alpha(m,n)). In particular, when m = \Omega(n \log n), \alpha(m,n) = O(1) and these time bounds are all linear in the number of edges, m.

But in the geometric setting, the graph is complete, so a time bound linear in the number of edges, m, is quadratic in the number of points, n. And indeed the best upper bounds for the Euclidean MST approach quadratic for large d, e.g., [CK95].

- Related Open Problems
This problem is intimately related to the bichromatic closest pair problem [AESW91].

- Appearances
- Categories
minimum spanning tree; shortest paths

- Entry Revision History
J. O’Rourke, 2 Aug. 2001; E. Demaine, 7 July 2002.

- [AESW91]
Pankaj K. Agarwal, Herbert Edelsbrunner, O. Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs.

*Discrete Comput. Geom.*, 6(5):407–422, 1991.- [Cha97]
Bernard Chazelle. A faster deterministic algorithm for minimum spanning trees. In

*Proc. 38th Annu. IEEE Sympos. Found. Comput. Sci.*, page To appear, 1997.- [Cha00b]
Bernard Chazelle. .

*J. ACM*, 47(6):1028–1047, November 2000.- [CK95]
P. B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields.

*J. Assoc. Comput. Mach.*, 42:67–90, 1995.- [GKFS96]
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, and Roman Smolensky. A lower bound for randomized algebraic decision trees. In

*Proc. 28th Annu. ACM Sympos. Theory Comput.*, pages 612–619, 1996.- [MO01]
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42.

*Internat. J. Comput. Geom. Appl.*, 11(5):573–582, 2001. Also in*SIGACT News*32(3):63-72 (2001), Issue 120.- [PR02]
Seth Pettie and Vijaya Ramachandran. An optimal minimum spanning tree algorithm.

*J. ACM*, 49(1):16–34, January 2002.