On Constructing Minimum Spanning Trees in <i>k</i>-Dimensional Spaces and Related Problems

Abstract

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_\infty $. By employing a subroutine that solves the post office problem, we show that, for fixed $k \geqq 3$, such a minimum spanning tree can be found in time $O(n^{2 - a(k)} (\log n)^{1 - a(k)} )$, where $a(k) = 2^{ - (k + 1)} $, The bound can be improved to $O((n\log n)^{1.8} )$ for points in 3-dimensional Euclidean space. We also obtain $o(n^2 )$ algorithms for finding a farthest pair in a set of n points and for other related problems.