| A minimal spanning tree algorithm for a point set in Euclidean space | |
| Authors: | J. Ernvall, J. Katajainen, and O. Nevalainen |
| Publication: | Report A28, Department of Computer Science, University of Turku (1980) |
| Full text: |  PDF (2.05 MB) |
| Abstract: | An algorithm for construction of a minimal spanning tree of a point set in k-dimensional Euclidean space is considered. Multiple subtrees, called point fragments, are formed in it. The minimal spanning tree is found by repeating a step in which the fragment of the minimal size is merged with the fragment which contains the point nearest to the first named fragment. Like in the algorithm of J.L.Bentley and J.H.Friedman (IEEE Trans. on Comp., p. 97, 1978) k-d tree structure and a number of priority queues are used for selecting the fragments to be connected by a new edge. At least for low dimensionalities the algorithm of this paper was fast when solving minimal spanning tree problems of normally distributed random points. |
| Related: |  HTML (Source code) HTML (Journal article) HTML (Thesis) |
| BibLATEX: | @report{EKN1980R,
author = {J. Ernvall and J. Katajainen and O. Nevalainen},
title = {A minimal spanning tree algorithm for a point set in {E}uclidean
space},
type = {Report},
number = {A28},
institution = {Department of Computer Science, University of Turku},
year = {1980},
}
|