Experiments with Computing Geometric Minimum Spanning Trees

G. Narasimhan, J. Zhu, Martin Tvede Zachariasen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of the 2nd Workshop on Algorithm Engineering and Experiments
Number of pages14
Publication statusPublished - 2000


Dive into the research topics of 'Experiments with Computing Geometric Minimum Spanning Trees'. Together they form a unique fingerprint.

Cite this