Relative neighborhood graph
Encyclopedia
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 p and q by an edge whenever there does not exist a third point r that is closer to both p and q 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.
. The relative neighborhood graph can be computed in linear time from the Delaunay triangulation
of the point set.
-based beta skeleton
. It is a subgraph of the Delaunay triangulation
, and the Euclidean minimum spanning tree
is a subgraph of it.
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. Although the Urquhart graph sometimes differs from the relative neighborhood graph it can be used as an approximation to the relative neighborhood graph.
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to both p and q than they are to each other. This graph was proposed by Godfried Toussaint
Godfried Toussaint
Godfried T. Toussaint is a Research Professor of Computer Science at New York University Abu Dhabi in Abu Dhabi, United Arab Emirates. He is an expert on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition , motion planning, visualization ,...
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.
Algorithms
showed how to construct the relative neighborhood graph efficiently in O(n log n) time. It can be computed in O (n) expected time, for random set of points distributed uniformly in the unit squareUnit square
In mathematics, a unit square is a square whose sides have length 1. Often, "the" unit square refers specifically to the square in the Cartesian plane with corners at , , , and .-In the real plane:...
. The relative neighborhood graph can be computed in linear time from the Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
of the point set.
Generalizations
Because it is defined only in terms of the distances between points, the relative neighborhood graph can be defined for point sets in any and for non-Euclidean metrics.Related graphs
The relative neighborhood graph is an example of a lensLens (geometry)
In geometry, a lens is a biconvex shape comprising two circular arcs, joined at their endpoints. If the arcs have equal radii, it is called a symmetric lens.A concave-convex shape is called a lune...
-based beta skeleton
Beta skeleton
In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane...
. It is a subgraph of the Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
, and the Euclidean minimum spanning tree
Euclidean minimum spanning tree
The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...
is a subgraph of it.
The Urquhart graph
Urquhart graph
In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation....
, 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. Although the Urquhart graph sometimes differs from the relative neighborhood graph it can be used as an approximation to the relative neighborhood graph.