Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions
Giri Narasimhan, Martin Zachariasen · ACM Journal of Experimental Algorithmics · 2001
Let S be a set of n points in ℜ d . We present an algorithm that uses the well-separated pair decomposition and computes the minimum spanning tree of S under any L p or polyhedral metric. A theoretical analysis shows that it has an expected running time of O(n log n ) for uniform point distributions; this is verified experimentally. Extensive experimental results show that this approach is practical. Under a variety of input distributions, the resulting implementation is robust and performs well for points in higher dimensional space.