Get Relative Neighborhood Graph essential facts below. View Videos or join the Relative Neighborhood Graph discussion. Add Relative Neighborhood Graph to your PopFlock.com topic list for future reference or share this resource on social media.
Relative Neighborhood Graph
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.
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. Although the Urquhart graph sometimes differs from the relative neighborhood graph it can be used as an approximation to the relative neighborhood graph.
^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.
^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.
^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.
^ abJaromczyk, 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.
^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.
^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.