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[editar]

Matemáticamente, dado un grafo $G=(V,E)$ , su grafo de vecindad relativa se define como $RNG(G)$ , cumpliendo:

$RNG(G)=\{uv\in E:(\not \exists w\in E:uw\in E,wv\in E,||uw||<||uv||,||wv||<||uv||)\}$

Algoritmos[editar]

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[editar]

↑ 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.

Datos: Q591159

[1] G. T. Toussaint: "The relative neighborhood graph of a finite planar set", Pattern Recognition, vol. 12, pp. 261-268, 1980.

[2] 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.

[3] 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.

[4] 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.

[1]

[2]

[3]

[4]