Experiments with Computing Geometric Minimum Spanning Trees

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.