| On the worst case of a minimal spanning tree algorithm for Euclidean space | |
| Author: | Jyrki Katajainen |
| Publication: | Report A34, Department of Computer Science, University of Turku (1982) |
| Full text: |  PDF (1.73 MB) |
| 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 (Journal article) HTML (Thesis) |
| BibLATEX: | @report{Kat1982aR,
author = {Jyrki Katajainen},
title = {On the worst case of a minimal spanning tree algorithm for
{E}uclidean space},
type = {Report},
number = {A34},
institution = {Department of Computer Science, University of Turku},
year = {1982},
}
|