relative neighborhood graph
File:Relative neighborhood graph.svg
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.{{citation
| last = Toussaint | first = G. T. | author-link = Godfried Toussaint
| doi = 10.1016/0031-3203(80)90066-7
| journal = Pattern Recognition
| pages = 261–268
| title = The relative neighborhood graph of a finite planar set
| volume = 12
| year = 1980
| issue = 4}}.{{citation
| last1 = Jaromczyk | first1 = J.W.
| last2 = Toussaint | first2 = G.T.
| doi = 10.1109/5.163414
| issue = 9
| journal = Proceedings of the IEEE
| pages = 1502–1517
| title = Relative neighborhood graphs and their relatives
| volume = 80
| year = 1992}}.
Algorithms
{{harvtxt|Supowit|1983}} showed how to construct the relative neighborhood graph of points in the plane efficiently in time.{{citation
| last = Supowit | first = K. J.
| doi = 10.1145/2402.322386
| issue = 3
| journal = Journal of the ACM
| pages = 428–448
| title = The relative neighborhood graph, with an application to minimum spanning trees
| volume = 30
| year = 1983| doi-access = free
}}. It can be computed in expected time, for random set of points distributed uniformly in the unit square.{{citation
| last1 = Katajainen | first1 = Jyrki
| last2 = Nevalainen | first2 = Olli
| last3 = Teuhola | first3 = Jukka
| doi = 10.1016/0020-0190(87)90225-0
| issue = 2
| journal = Information Processing Letters
| pages = 77–86
| title = A linear expected-time algorithm for computing planar relative neighbourhood graphs
| volume = 25
| year = 1987}}. The relative neighborhood graph can be computed in linear time from the Delaunay triangulation of the point set.{{citation
| last1 = Jaromczyk | first1 = J. W.
| last2 = Kowaluk | first2 = M.
| contribution = A note on relative neighborhood graphs
| doi = 10.1145/41958.41983
| location = New York, NY, USA
| pages = 233–241
| publisher = ACM
| title = Proc. 3rd Symp. Computational Geometry
| year = 1987| isbn = 0-89791-231-4
}}.{{citation
| last = Lingas | first = A.
| doi = 10.1016/0925-7721(94)90018-3
| issue = 4
| journal = Computational Geometry
| pages = 199–208
| title = A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
| volume = 4
| year = 1994| doi-access = free
}}.
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 {{nowrap|dimension,{{citation
| last1 = Jaromczyk | first1 = J. W.
| last2 = Kowaluk | first2 = M.
| doi = 10.1016/0166-218X(91)90069-9
| issue = 2
| journal = Discrete Applied Mathematics
| pages = 181–191
| title = Constructing the relative neighborhood graph in 3-dimensional Euclidean space
| volume = 31
| year = 1991| doi-access = free
}}.{{citation
| last1 = Agarwal | first1 = Pankaj K. | author1-link = Pankaj K. Agarwal
| last2 = Mataušek | first2 = Jiří | author2-link = Jiří Matoušek (mathematician)
| contribution = Relative neighborhood graphs in three dimensions
| pages = 58–65
| title = Proc. 3rd ACM–SIAM Symp. Discrete Algorithms
| contribution-url = http://portal.acm.org/citation.cfm?id=139404.139416
| year = 1992}}.}} and for non-Euclidean metrics.{{citation
| last = O'Rourke | first = J. | author-link = Joseph O'Rourke (professor)
| doi = 10.1016/0031-3203(82)90070-X
| issue = 3
| journal = Pattern Recognition
| pages = 189–192
| title = Computing the relative neighborhood graph in the and metrics
| volume = 15
| year = 1982}}.{{citation
| last = Lee | first = D. T. | author-link = Der-Tsai Lee
| doi = 10.1016/0031-3203(85)90023-8
| issue = 5
| journal = Pattern Recognition
| pages = 327–332
| title = Relative neighborhood graphs in the -metric
| volume = 18
| year = 1985}}. Computing the relative neighborhood graph, for higher-dimensional point sets, can be done in time .
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.{{citation
| last = Urquhart | first = R. B.
| doi = 10.1049/el:19800386
| issue = 14
| journal = Electronics Letters
| pages = 556–557
| title = Algorithms for computation of relative neighborhood graph
| volume = 16
| year = 1980}}. Although the Urquhart graph sometimes differs from the relative neighborhood graph{{citation
| last = Toussaint | first = G. T. | author-link = Godfried Toussaint
| doi = 10.1049/el:19800611
| issue = 22
| journal = Electronics Letters
| page = 860
| title = Comment: Algorithms for computing relative neighborhood graph
| volume = 16
| year = 1980}}. Reply by Urquhart, pp. 860–861. it can be used as an approximation to the relative neighborhood graph.{{citation
| last1 = Andrade | first1 = Diogo Vieira
| last2 = de Figueiredo | first2 = Luiz Henrique
| contribution = Good approximations for the relative neighbourhood graph
| title = Proc. 13th Canadian Conference on Computational Geometry
| contribution-url = https://web.archive.org/web/20190328183825/https://rutcor.rutgers.edu/~dandrade/papers/ug.pdf
| year = 2001}}.
References
{{reflist}}