On the worst case of a minimal spanning tree algorithm for euclidean space |
| |
| Authors: | Jyrki Katajainen |
| |
| Affiliation: | 1. Department of Mathematical Sciences, University of Turku, SF-20500, Turku 50, Finland
|
| |
| Abstract: | This paper concerns the worst case running time of the minimal spanning tree algorithm presented by Bentley and Friedman. For a set ofN points ink-dimensional Euclidean space the worst case performance of the algorithm is shown to beΘ(N 2 logN), fork≧2 andΘ(N 2), fork=1. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
