Let S be a set of n points in <d. We present analgorithm that uses the well-separated pair decomposition and computes the minimum spanning tree of S under any Lp or polyhedral metric. It has an expected running time of O(n log n)for uniform distributions. Experimental resultsshow that this approach is practical. Under a variety of input distributions, the resulting implementation is robust and performs well for pointsin higher dimensional space.
|Title of host publication||Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments|
|Number of pages||14|
|Publication status||Published - 2000|