| A linear expected-time algorithm for computing planar relative neighbourhood graphs | |
| Authors: | Jyrki Katajainen, Olli Nevalainen, and Jukka Teuhola |
| Published in: | Information Processing Letters 25,2 (1987), 77-86 |
| Full text: |  PDF (659 kB) |
| DOI: | 10.1016/0020-0190(87)90225-0 |
| Copyright: | © Elsevier Science Publishers B.V. |
| Abstract: | A new algorithm for computing the relative neighbourhood graph (RNG) of a planar point set is given. The expected running time of the algorithm is linear for a point set in a unit square when the points have been generated by a homogeneous planar Poisson point process. The worst-case running time is quadratic on the number of the points. The algorithm proceeds in two steps. First, a supergraph of the RNG is constructed with the aid of a cell organization of the points. Here, a point is connected by an edge to some of its nearest neighbours in eight regions around the point. The nearest region neighbours are chosen in a special way to minimize the costs. Second, extra edges are pruned from the graph by a simple scan. |
| Related: |  HTML (Thesis) |
| BibLATEX: | @article{KNT1987J,
author = {Jyrki Katajainen and Olli Nevalainen and Jukka Teuhola},
title = {A linear expected-time algorithm for computing planar relative
neighbourhood graphs},
journaltitle = {Information Processing Letters},
volume = {25},
number = {2},
year = {1987},
pages = {77--86},
}
|