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 (n^2 - a (k) (n) ^1 - a (k) ), where a (k) = 2^ - (k + 1), The bound can be improved to O ( (n 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.