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]

The relative neighborhood graph of 100 random points in a unit square.

Algorithms

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]

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]

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. 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. 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).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.