Geometric minimum spanning trees via well-separated pair decompositions Article

Narasimhan, G, Zachariasen, M. (2001). Geometric minimum spanning trees via well-separated pair decompositions . 6 10.1145/945394.945400

cited authors

  • Narasimhan, G; Zachariasen, M

fiu authors

abstract

  • Let S be a set of n points in Rd. We present an algorithm that uses the well-separated pair decomposition and computes the minimum spanning tree of S under any Lp or polyhedral metric. A theoretical analysis shows that it has an expected running time of 0(nlog 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.

publication date

  • January 1, 2001

Digital Object Identifier (DOI)

volume

  • 6