Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions

Giri Narasimhan, Martin Zachariasen

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


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 Lp 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.
Original languageEnglish
Number of pages6
JournalA C M Journal of Experimental Algorithmics
Publication statusPublished - 2001


  • computational geometry
  • experimental algorithmics
  • algorithm design and analysis
  • geometric minimum spanning trees


Dive into the research topics of 'Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions'. Together they form a unique fingerprint.

Cite this