A Fast Approximation Algorithm For Minimum Spanning Trees In K-Dimensional Space
Pravin M. Vaidya · 1984
We study the problem of finding a minimum spanning tree on the complete graph on n points in Ek, 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 Lq, 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)).