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.gif>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.gif>HTML (Source code)  <html.gif>HTML (Journal article)  <html.gif>HTML (Thesis)  
  author = {J. Ernvall and J. Katajainen and O. Nevalainen},
  title = {A minimal spanning tree algorithm for a point set in {E}uclidean
  type = {Report},
  number = {A28},
  institution = {Department of Computer Science, University of Turku},
  year = {1980},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.