- Grafo de vecindad relativa
-
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 Toussaint[1] en 1980, y desde entonces ha sido objeto de cuantiosa investigación.
Definición
Matemáticamente, dado un grafo G = (V,E), su grafo de vecindad relativa se define como RNG(G), cumpliendo:
Algoritmos
Supowit (1983) demostró que es posible construir eficientemente grafos de vecindad relativa en un tiempo O(nlog(n)).[2] Para vértices aleatorios distribuidos uniformemente en un cuadrado, el Relative Neighbor Graph se puede calcular en un tiempo O(n).[3] Además, se puede computar en un tiempo lineal a partir de la triangulación de Delaunay del conjunto de puntos (vértices).[4]
Referencias
- ↑ G. T. Toussaint: "The relative neighborhood graph of a finite planar set", Pattern Recognition, vol. 12, pp. 261-268, 1980.
- ↑ 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.
- ↑ 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.
- ↑ 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.
Categoría:- Algoritmos de computación gráfica
Wikimedia foundation. 2010.
