A Fast Approximation Algorithm For Minimum Spanning Trees In K-Dimensional Space

We study the problem of finding a minimum spanning tree on the complete graph on n points in E^k, with the weight of an edge between any two points being the distance between the two points under some distance metric. A fast algorithm, which finds an approximate minimum spanning tree with weight at most (1+ϵ) times optimal O(nlogn((logn)^k + log (ϵ^-1)(logn)^k-1ϵ^{-(k-1))) time, is developed for the L_q, q =2,3, ..., distance metrics. Moreover, if the n points are assumed to be independently and uniformly distributed in the box [0,l]_k}, then the probability that the approximate minimum spanning tree found is an exact minimum spanning tree is shown to be (1 -o(l/n)).