En geometría computacional, el Grafo de vecindad relativa (Relative Neighborhood Graph, RNG por sus siglas en inglés) es el subgrafo que extrae las aristas entre los vértices más próximos (respecto a una métrica dada) de un grafo genérico. Fue propuesto por Godfried ToussaintG. T. Toussaint: "The relative neighborhood graph of a finite planar set", Pattern Recognition, vol. 12, pp. 261-268, 1980. en 1980, y desde entonces ha sido objeto de cuantiosa investigación.
Definición
Matemáticamente, dado un grafo , su grafo de vecindad relativa se define como , cumpliendo:
Algoritmos
Supowit (1983) demostró que es posible construir eficientemente grafos de vecindad relativa en un tiempo .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. Para vértices aleatorios distribuidos uniformemente en un cuadrado, el Relative Neighbor Graph se puede calcular en un tiempo .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. Además, se puede computar en un tiempo lineal a partir de la triangulación de Delaunay del conjunto de puntos (vértices).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.
Referencias
Categoría:Algoritmos de computación gráfica