On the worst case of a minimal spanning tree algorithm for Euclidean space
Author:Jyrki Katajainen
Published in:BIT 23,1 (1983), 2-8
Full text:<pdf.gif>PDF (710 kB)  
DOI:10.1007/BF01937321
Copyright:© Springer
Abstract:   This paper concerns the worst case running time of the minimal spanning tree algorithm presented by Bentley and Friedman.

   For a set of N points in k-dimensional Euclidean space the worst case performance of the algorithm is shown to be Θ(N2 log N), for k ≥ 2 and Θ(N2), for k = 1.

Related:<html.gif>HTML (Technical report)  <html.gif>HTML (Thesis)  
BibLATEX:
@article{Kat1983aJ,
  author = {Jyrki Katajainen},
  title = {On the worst case of a minimal spanning tree algorithm for
    {E}uclidean space},
  journaltitle = {BIT},
  volume = {23},
  number = {1},
  year = {1983},
  pages = {2--8},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 22.05.2015.