Computing relative neighbourhood graphs in the plane

摘要

The relative neighbourhood graph (RNG) of a set of N points connects the relative neighbours, i.e. a pair of points is connected by an edge if those points are at least as close to each other as to any other point. The paper presents two new algorithms for constructing RNG in two-dimensional Euclidean space. The method is to determine a supergraph for RNG which can then be thinned efficiently from the extra edges. The first algorithm is simple, and works in O(N2) time. The worst case running time of the second algorithm is also O(N2), but its average case running time is O(N) for points from a homogeneous planar Poisson point process. Experimental tests have shown the usefulness of the approach.