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 and by an edge whenever there does not exist a third point that is closer to both and 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]
Algorithms
editSupowit (1983) showed how to construct the relative neighborhood graph of points in the plane efficiently in time.[3] It can be computed in 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]
Generalizations
editBecause 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] Computing the relative neighborhood graph, for higher-dimensional point sets, can be done in time .
Related graphs
editThe 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]
References
edit- ^ 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.
- ^ 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", Journal of the 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.
- ^ 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, ISBN 0-89791-231-4.
- ^ 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 Applied Mathematics, 31 (2): 181–191, doi:10.1016/0166-218X(91)90069-9.
- ^ Agarwal, Pankaj K.; Mataušek, Jiří (1992), "Relative neighborhood graphs in three dimensions", Proc. 3rd ACM–SIAM Symp. Discrete Algorithms, pp. 58–65.
- ^ O'Rourke, J. (1982), "Computing the relative neighborhood graph in the and metrics", Pattern Recognition, 15 (3): 189–192, doi:10.1016/0031-3203(82)90070-X.
- ^ Lee, D. T. (1985), "Relative neighborhood graphs in the -metric", Pattern Recognition, 18 (5): 327–332, doi:10.1016/0031-3203(85)90023-8.
- ^ Urquhart, R. B. (1980), "Algorithms for computation of relative neighborhood graph", Electronics Letters, 16 (14): 556–557, doi:10.1049/el:19800386.
- ^ 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.
- ^ Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001), "Good approximations for the relative neighbourhood graph" (PDF), Proc. 13th Canadian Conference on Computational Geometry.
