Next: Problem 6: Minimum Euclidean Matching in 2D
Previous: Problem 4: Union of Fat Objects in 3D
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]?
Uncertain, pending investigation.
Open.
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].
This problem is intimately related to the bichromatic closest pair problem [AESW91].
minimum spanning tree; shortest paths
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., pages 22–31, 1997.
Bernard Chazelle. . 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.