Relative neighborhood graph

From Wikipedia, the free encyclopedia

In computational geometry, the relative neighborhood graph (RNG) was proposed by Godfried Toussaint in 1980.[1] There has been a lot of research on this kind of graph.[2][3]

[edit] Definition

The relative neighborhood graph of a graph G = (V, E), denoted by RNG(G), is the set of all edges uv є E such that there is no vertex or point w where uw є E, wv є E and ||uw|| < ||uv|| and ||wv|| < ||uv||.

[edit] References

  1. ^ G. T. Toussaint, “The relative neighborhood graph of a finite planar set,” Pattern Recognition, vol. 12, pp. 261-268, 1980.
  2. ^ Welcome to IEEE Xplore 2.0: Relative neighborhood graphs and their relatives
  3. ^ The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees


 This geometry-related article is a stub. You can help Wikipedia by expanding it.