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 ${\displaystyle p}$ and ${\displaystyle q}$ by an edge whenever there does not exist a third point ${\displaystyle r}$ that is closer to both ${\displaystyle p}$ and ${\displaystyle 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.