Relative neighborhood graph

In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points

[1][2] Supowit (1983) showed how to construct the relative neighborhood graph of

expected time, for random set of points distributed uniformly in the unit square.

[4] The relative neighborhood graph can be computed in linear time from the Delaunay triangulation of the point set.

[5][6] Because it is defined only in terms of the distances between points, the relative neighborhood graph can be defined for point sets in any dimension,[1][7][8] and for non-Euclidean metrics.

[1][5][9][10] Computing the relative neighborhood graph, for higher-dimensional point sets, can be done in time

The relative neighborhood graph is an example of a lens-based beta skeleton.

In turn, the Euclidean minimum spanning tree is a subgraph of it, from which it follows that it is a connected graph.