En geometría computacional , el gráfico de vecindad relativa (RNG ) es un gráfico no dirigido definido en un conjunto de puntos en el plano euclidiano conectando dos puntos y por un borde siempre que no exista un tercer punto que esta mas cerca de ambos y de lo que son el uno para el otro. Este gráfico fue propuesto por Godfried Toussaint en 1980 como una forma de definir una estructura a partir de un conjunto de puntos que coincidirían con las percepciones humanas de la forma del conjunto. [1] [2]
Algoritmos
Supowit (1983) mostró cómo construir el gráfico de vecindad relativa de manera eficiente enhora. [3] Se puede calcular en tiempo esperado , para un conjunto aleatorio de puntos distribuidos uniformemente en el cuadrado unitario . [4] El gráfico de vecindad relativa se puede calcular en tiempo lineal a partir de la triangulación de Delaunay del conjunto de puntos. [5] [6]
Generalizaciones
Debido a que se define solo en términos de las distancias entre puntos, el gráfico de vecindad relativa se puede definir para conjuntos de puntos en cualquier dimensión, [1] [7] [8] y para métricas no euclidianas. [1] [5] [9] [10]
Gráficos relacionados
El gráfico de vecindad relativa es un ejemplo de un esqueleto beta basado en lentes . Es un subgrafo de la triangulación de Delaunay . A su vez, el árbol de expansión mínimo euclidiano es un subgráfico del mismo, de lo que se sigue que es un gráfico conectado .
El gráfico de Urquhart , el gráfico formado al eliminar el borde más largo de cada triángulo en la triangulación de Delaunay, se propuso originalmente como un método rápido para calcular el gráfico de vecindad relativa. [11] Aunque el gráfico de Urquhart a veces difiere del gráfico de vecindad relativa [12], se puede utilizar como una aproximación al gráfico de vecindad relativa. [13]
Referencias
- ^ a b c Toussaint, GT (1980), "El gráfico de vecindad relativa de un conjunto plano finito", Reconocimiento de patrones , 12 (4): 261-268, doi : 10.1016 / 0031-3203 (80) 90066-7.
- ^ Jaromczyk, JW; Toussaint, GT (1992), "Gráficos de vecindad relativa y sus parientes", Actas del IEEE , 80 (9): 1502-1517, doi : 10.1109 / 5.163414.
- ^ Supowit, KJ (1983), "El gráfico de vecindad relativa, con una aplicación a árboles de expansión mínimos", Journal of the ACM , 30 (3): 428–448, doi : 10.1145 / 2402.322386.
- ^ Katajainen, Jyrki; Nevalainen, Olli; Teuhola, Jukka (1987), "Un algoritmo lineal de tiempo esperado para calcular gráficos de vecindad relativa plana", Information Processing Letters , 25 (2): 77-86, doi : 10.1016 / 0020-0190 (87) 90225-0.
- ^ a b Jaromczyk, JW; Kowaluk, M. (1987), "Una nota sobre gráficos de vecindad relativa", Proc. 3rd Symp. Geometría computacional , Nueva York, NY, EE. UU .: ACM, págs. 233–241, doi : 10.1145 / 41958.41983.
- ^ Lingas, A. (1994), "Una construcción en tiempo lineal del gráfico de vecindad relativa de la triangulación de Delaunay", Geometría computacional , 4 (4): 199-208, doi : 10.1016 / 0925-7721 (94) 90018-3.
- ^ Jaromczyk, JW; Kowaluk, M. (1991), "Construyendo el gráfico de vecindad relativa en el espacio euclidiano tridimensional", Matemáticas aplicadas discretas , 31 (2): 181-191, doi : 10.1016 / 0166-218X (91) 90069-9.
- ^ Agarwal, Pankaj K .; Mataušek, Jiří (1992), "Gráficos de vecindad relativa en tres dimensiones" , Proc. 3er ACM – SIAM Symp. Algoritmos discretos , págs. 58–65.
- ^ O'Rourke, J. (1982), "Calcular el gráfico de vecindad relativa en el y métricas ", reconocimiento de patrones , 15 (3): 189-192, doi : 10.1016 / 0031-3203 (82) 90070-X.
- ^ Lee, DT (1985), "Gráficos de vecindad relativa en el-metric ", reconocimiento de patrones , 18 (5): 327–332, doi : 10.1016 / 0031-3203 (85) 90023-8.
- ^ Urquhart, RB (1980), "Algoritmos para el cálculo del gráfico de vecindad relativa", Electronics Letters , 16 (14): 556–557, doi : 10.1049 / el: 19800386.
- ^ Toussaint, GT (1980), "Comentario: Algoritmos para calcular el gráfico de vecindad relativa", Electronics Letters , 16 (22): 860, doi : 10.1049 / el: 19800611. Respuesta de Urquhart, págs. 860–861 .
- ^ Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001), "Buenas aproximaciones para el gráfico de vecindad relativa" (PDF) , Proc. 13a Conferencia Canadiense de Geometría Computacional.