Algorithms
Supowit (1983) 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 square. The relative neighborhood graph can be computed in linear time from the Delaunay triangulation of the point set.
Read more about this topic: Relative Neighborhood Graph