Relative neighborhood graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The relative neighborhood graph of 100 random points in a unit square.

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 p and q by an edge whenever there does not exist a third point r that is closer to both p and 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.[1][2]


Supowit (1983) showed how to construct the relative neighborhood graph efficiently in O(n log n) time.[3] It can be computed in O (n) expected time, for random set of points distributed uniformly in the unit square.[4] The relative neighborhood graph can be computed in linear time from the Delaunay triangulation of the point set.[5][6]


Because it is defined only in terms of the distances between points, the relative neighborhood graph can be defined for point sets in any dimension,[1][7][8] and for non-Euclidean metrics.[1][5][9][10]

Related graphs[edit]

The relative neighborhood graph is an example of a lens-based beta skeleton. It is a subgraph of the Delaunay triangulation. In turn, the Euclidean minimum spanning tree is a subgraph of it, from which it follows that it is a connected graph.

The Urquhart graph, the graph formed by removing the longest edge from every triangle in the Delaunay triangulation, was originally proposed as a fast method to compute the relative neighborhood graph.[11] Although the Urquhart graph sometimes differs from the relative neighborhood graph[12] it can be used as an approximation to the relative neighborhood graph.[13]


  1. ^ a b c Toussaint, G. T. (1980), "The relative neighborhood graph of a finite planar set", Pattern Recognition, 12 (4): 261–268, doi:10.1016/0031-3203(80)90066-7 .
  2. ^ Jaromczyk, J.W.; Toussaint, G.T. (1992), "Relative neighborhood graphs and their relatives", Proceedings of the IEEE, 80 (9): 1502–1517, doi:10.1109/5.163414 .
  3. ^ Supowit, K. J. (1983), "The relative neighborhood graph, with an application to minimum spanning trees", J. ACM, 30 (3): 428–448, doi:10.1145/2402.322386 .
  4. ^ Katajainen, Jyrki; Nevalainen, Olli; Teuhola, Jukka (1987), "A linear expected-time algorithm for computing planar relative neighbourhood graphs", Information Processing Letters, 25 (2): 77–86, doi:10.1016/0020-0190(87)90225-0 .
  5. ^ a b Jaromczyk, J. W.; Kowaluk, M. (1987), "A note on relative neighborhood graphs", Proc. 3rd Symp. Computational Geometry, New York, NY, USA: ACM, pp. 233–241, doi:10.1145/41958.41983 .
  6. ^ Lingas, A. (1994), "A linear-time construction of the relative neighborhood graph from the Delaunay triangulation", Computational Geometry, 4 (4): 199–208, doi:10.1016/0925-7721(94)90018-3 .
  7. ^ Jaromczyk, J. W.; Kowaluk, M. (1991), "Constructing the relative neighborhood graph in 3-dimensional Euclidean space", Discrete Appl. Math., 31 (2): 181–191, doi:10.1016/0166-218X(91)90069-9 .
  8. ^ Agarwal, Pankaj K.; Mataušek, Jiří (1992), "Relative neighborhood graphs in three dimensions", Proc. 3rd ACM–SIAM Symp. Discrete Algorithms, pp. 58–65 .
  9. ^ O'Rourke, J. (1982), "Computing the relative neighborhood graph in the L1 and L metrics", Pattern Recognition, 15 (3): 189–192, doi:10.1016/0031-3203(82)90070-X .
  10. ^ Lee, D. T. (1985), "Relative neighborhood graphs in the L1-metric", Pattern Recognition, 18 (5): 327–332, doi:10.1016/0031-3203(85)90023-8 .
  11. ^ Urquhart, R. B. (1980), "Algorithms for computation of relative neighborhood graph", Electronics Letters, 16 (14): 556–557, doi:10.1049/el:19800386 .
  12. ^ Toussaint, G. T. (1980), "Comment: Algorithms for computing relative neighborhood graph", Electronics Letters, 16 (22): 860, doi:10.1049/el:19800611 . Reply by Urquhart, pp. 860–861.
  13. ^ Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001), "Good approximations for the relative neighbourhood graph", Proc. 13th Canadian Conference on Computational Geometry (PDF) .