On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

The problem of finding a minimum spanning tree connecting n points in a k-dimensional space is discussed under three common distance metrics: Euclidean, rectilinear, and L_∞. By employing a subroutine that solves the post office problem, we show that, for fixed k 3, such a minimum spanning tree can be found in time O(n2 - a(k) (log n)1 - a(k) ), where a(k) = 2- (k + 1), The bound can be improved to O((nlog n)1.8 ) for points in 3-dimensional Euclidean space. We also obtain o(n² ) algorithms for finding a farthest pair in a set of n points and for other related problems.