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(N^{2})
time. The worst case running time of the second algorithm is also
O(N^{2}), 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.

@article{KN1986J,
author = {Jyrki Katajainen and Olli Nevalainen},
title = {Computing relative neighbourhood graphs in the plane},
journaltitle = {Pattern Recognition},
volume = {19},
number = {3},
year = {1986},
pages = {221--228},
}