| Finding minimal spanning trees in a Euclidean coordinate space | |
| Authors: | O. Nevalainen, J. Ernvall, and J. Katajainen |
| Published in: | BIT 21,1 (1981), 46-54 |
| Full text: |  PDF (926 kB) |
| DOI: | 10.1007/BF01934070 |
| Copyright: | © Springer |
| Abstract: | The minimal spanning tree problem of a point set in a k-dimensional Euclidean space is considered and a new version of the multifragment MST-algorithm of Bentley and Friedman is given. The minimal spanning tree is found by repeatedly joining the minimal subtree with the closest subtree. A k-d tree is used for choosing the connecting edges. Computation time of the algorithm depends on the configuration of the point set: for normally distributed random points the algorithm is very fast. Two extreme cases demanding O(n log n) and O(n2) operations, n being the cardinality of the point set, are also given |
| Related: |  HTML (Technical report) HTML (Source code) |
| BibLATEX: | @article{NEK1981J,
author = {O. Nevalainen and J. Ernvall and J. Katajainen},
title = {Finding minimal spanning trees in a {E}uclidean coordinate space},
journaltitle = {BIT},
volume = {21},
number = {1},
year = {1981},
pages = {46--54},
}
|