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.gif>PDF (926 kB)  
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.gif>HTML (Technical report)  <html.gif>HTML (Source code)  
  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},
This page was generated by Jyrki Katajainen <> on 31.12.2011.