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 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 \exists 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))$. Para vértices aleatorios distribuidos uniformemente en un cuadrado, el Relative Neighbor Graph se puede calcular en un tiempo $O(n)$. Además, se puede computar en un tiempo lineal a partir de la triangulación de Delaunay del conjunto de puntos (vértices).

