next up previous
Next: Problem 6: Minimum Euclidean Up: The Open Problems Project Previous: Problem 4: Union of

Problem 5: Euclidean Minimum Spanning Tree

Can the Euclidean minimum spanning tree (MST) of n points in $ \mathbb {R}$d be computed in time close to the lower bound of Ω(n log n) [GKFS96]?
Uncertain, pending investigation.
Partial and Related Results
Several algorithms have been developed for general graphs with arbitrary edge weights. Chazelle presented an O((m, n)logα(m, n))-time algorithm [Cha97], and then an O((m, n))-time algorithm [Cha00b], where α(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 Ω(m) and O((m, n)). In particular, when m = Ω(n log n), α(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].
minimum spanning tree; shortest paths
Entry Revision History
J. O'Rourke, 2 Aug. 2001; E. Demaine, 7 July 2002.


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.

Bernard Chazelle.
A faster deterministic algorithm for minimum spanning trees.
In Proc. 38th Annu. IEEE Sympos. Found. Comput. Sci., page To appear, 1997.

Bernard Chazelle.
A minimum spanning tree algorithm with inverse-Ackermann type complexity.
J. ACM, 47(6):1028-1047, November 2000.

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.

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.

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.

Seth Pettie and Vijaya Ramachandran.
An optimal minimum spanning tree algorithm.
J. ACM, 49(1):16-34, January 2002.

next up previous
Next: Problem 6: Minimum Euclidean Up: The Open Problems Project Previous: Problem 4: Union of
The Open Problems Project - December 08, 2012