 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.