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 and by an edge whenever there does not exist a third point that is closer to both and than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set. [1] [2]
Supowit (1983) showed how to construct the relative neighborhood graph of points in the plane efficiently in time. [3] It can be computed in 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. It is a subgraph of the Delaunay triangulation. In turn, the Euclidean minimum spanning tree is a subgraph of it, from which it follows that it is a connected graph.
The Urquhart graph, the graph formed by removing the longest edge from every triangle in the Delaunay triangulation, was originally proposed as a fast method to compute the relative neighborhood graph. [11] Although the Urquhart graph sometimes differs from the relative neighborhood graph [12] it can be used as an approximation to the relative neighborhood graph. [13]
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 and by an edge whenever there does not exist a third point that is closer to both and than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set. [1] [2]
Supowit (1983) showed how to construct the relative neighborhood graph of points in the plane efficiently in time. [3] It can be computed in 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. It is a subgraph of the Delaunay triangulation. In turn, the Euclidean minimum spanning tree is a subgraph of it, from which it follows that it is a connected graph.
The Urquhart graph, the graph formed by removing the longest edge from every triangle in the Delaunay triangulation, was originally proposed as a fast method to compute the relative neighborhood graph. [11] Although the Urquhart graph sometimes differs from the relative neighborhood graph [12] it can be used as an approximation to the relative neighborhood graph. [13]