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


Problem 5: Euclidean Minimum Spanning Tree

Statement
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]?
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, 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].
Appearances
[MO01]
Categories
minimum spanning tree; shortest paths
Entry Revision History
J. O'Rourke, 2 Aug. 2001; E. Demaine, 7 July 2002.

Bibliography

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.
A minimum spanning tree algorithm with inverse-Ackermann type complexity.
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.


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