A linear expected-time algorithm for computing planar relative neighbourhood graphs |
| |
| Affiliation: | 1. Universität Trier FB 4, Abteilung Informatik, 54286 Trier, Germany;2. Department of Informatics, University of Bergen, 5020 Bergen, Norway;3. The Institute of Mathematical Sciences, Chennai 600 113, India;4. Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany;1. Department of Computer Engineering and Systems, Alexandria University, Egypt;2. Department of Computer Science, University of Copenhagen, Denmark;3. School of Computer Science and Engineering, Seoul National University, South Korea |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
