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 $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]

YouTube Encyclopedic

1/3
Views:
7 207
8 720
1 152

Transcription

Algorithms

Supowit (1983) showed how to construct the relative neighborhood graph of $n$ points in the plane 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]

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 $O(n^{2})$ .

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

^ ^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.
^ 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 $L_{1}$ and $L_{\infty }$ metrics", Pattern Recognition, 15 (3): 189–192, doi:10.1016/0031-3203(82)90070-X.
^ Lee, D. T. (1985), "Relative neighborhood graphs in the $L_{1}$ -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.

This page was last edited on 24 March 2024, at 04:43

From Wikipedia, the free encyclopedia