Minimum Spanning Trees in k -Dimensional Space
Pravin M. Vaidya · SIAM Journal on Computing · 1988
We study the problem of finding a minimum spanning tree in the complete graph on a set V of n points in k-dimensional space. The points are the vertices of this graph and the weight of an edge between two points is the distance between the points under some $L_q $ metric. We give an $O(\varepsilon ^{ - k} n\log n)$ algorithm for finding an approximate minimum spanning tree in such a graph; the weight of the approximate minimum spanning tree is guaranteed to be at most $(1 + \varepsilon )$ times the weight of a minimum spanning tree. We also present an algorithm to find a minimum spanning tree in the complete graph on V. Under the assumption that V consists of n random points, independently and uniformly distributed in the unit k-cube $[0,1]^k $, the expected running time of this minimum spanning tree algorithm is shown to be $O(n\alpha (cn,n))$ where c is a constant dependent on k and $\alpha $ is the inverse Ackermann function.