The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees

The relative neighborhood graph (RNG) of a set V of pomts in Euchdean space is the graph (V, E), where (p, q) E E iff there is no point z E V such that d(p, z) < d(p, q) and d(q, z) < d(p, q) It is shown that (1) the RNG of n points in the' plane can be found in O(n log n) time, which is optimal to wRlun a multiphcative constant. (2) The RNG, as well as the minimum spanning tree, of the vertices of a convex, n-vertex polygon can be found m O(n) time, given the vertices m sorted clockwise order.