Graphe de voisinage relatif

En géométrie algorithmique, le graphe de voisinage relatif (en anglais relative neighborhood graph, souvent abrégé RNG) est un graphe non orienté qui connecte un ensemble de points dans un espace euclidien. Plus précisément, il connecte deux points $p$ et $q$ si et seulement s'il n'existe pas de troisième point $r$ qui soit plus proche de $p$ et de $q$ qu'ils ne le sont entre eux. Il est introduit en 1980 par Godfried Toussaint (en).

Graphe de voisinage relatif de 100 points placés aléatoirement dans un carré.

Définition

Le graphe de voisinage relatif d'un nuage de points $P\subset \mathbb {R} ^{d}$ a pour arêtes $\{(a,b)\in P^{2}\mid \not \exists x\in P,d(a,x)<d(a,b){\text{ et }}d(b,x)<d(a,b)\}$ où $d$ est la distance euclidienne.

Algorithmes

Supowit montre en 1983 que le graphe de voisinage relatif dans le plan euclidien peut être calculé en ${\mathcal {O}}(n\log n)$. Il peut également être calculé en ${\mathcal {O}}(n)$ à partir de la triangulation de Delaunay.

Plus généralement, dans un espace de dimension $d$, il peut être calculé en ${\mathcal {O}}(n^{2})$. Il est également possible de le calculer avec un algorithme probabiliste avec une complexité en moyenne en ${\mathcal {O}}\left(n^{2\left(1-{\frac {1}{d+1}}\right)+\varepsilon }\right)$.

Relations avec d'autres graphes

Si l'arête rouge est dans le graphe de voisinage relatif, la lentille en blanc est vide.

Le graphe de voisinage relatif est un sous-graphe de la triangulation de Delaunay, du graphe de Gabriel, ainsi que du graphe d'Urquhart. Inversement, l'arbre couvrant de poids minimal euclidien est un sous-graphe du graphe de voisinage relatif.