| 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 (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 (Technical report) 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},
}
|