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 $\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

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