Relative neighborhood graph
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 [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] by an edge whenever there does not exist a third point [math]\displaystyle{ r }[/math] that is closer to both [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] 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
(Supowit 1983) showed how to construct the relative neighborhood graph of [math]\displaystyle{ n }[/math] points in the plane efficiently in [math]\displaystyle{ O(n\log n) }[/math] time.[3] It can be computed in [math]\displaystyle{ O(n) }[/math] 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
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] Computing the relative neighborhood graph, for higher-dimensional point sets, can be done in time [math]\displaystyle{ O(n^2) }[/math].
Related graphs
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]
References
- ↑ 1.0 1.1 1.2 "The relative neighborhood graph of a finite planar set", Pattern Recognition 12 (4): 261–268, 1980, 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.
- ↑ 5.0 5.1 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.
- ↑ 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.
- ↑ "Relative neighborhood graphs in three dimensions", Proc. 3rd ACM–SIAM Symp. Discrete Algorithms, 1992, pp. 58–65, http://portal.acm.org/citation.cfm?id=139404.139416.
- ↑ "Computing the relative neighborhood graph in the [math]\displaystyle{ L_1 }[/math] and [math]\displaystyle{ L_\infty }[/math] metrics", Pattern Recognition 15 (3): 189–192, 1982, doi:10.1016/0031-3203(82)90070-X.
- ↑ "Relative neighborhood graphs in the [math]\displaystyle{ L_1 }[/math]-metric", Pattern Recognition 18 (5): 327–332, 1985, 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.
- ↑ "Comment: Algorithms for computing relative neighborhood graph", Electronics Letters 16 (22): 860, 1980, 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", Proc. 13th Canadian Conference on Computational Geometry, http://rutcor.rutgers.edu/~dandrade/papers/ug.pdf.
 |  |
