Grafo de vecindad relativa

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:

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

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

  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.

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”