Graphe de voisinage relatif

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

En géométrie algorithmique, le graphe de voisinage relatif (en anglais Modèle:Langue, 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 Modèle:Lien.

Définition

Le graphe de voisinage relatif d'un nuage de points $P\subset {ℝ}^d$ a pour arêtes $\{(a,b)\in P^2\mid \mathrm{\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 $𝒪(n\log n)$. Il peut également être calculé en $𝒪(n)$ à partir de la triangulation de Delaunay.

Plus généralement, dans un espace de dimension $d$, il peut être calculé en $𝒪(n^2)$. Il est également possible de le calculer avec un algorithme probabiliste avec une complexité en moyenne en $𝒪\left(n^{2(1-\frac{1}{d+1})+\epsilon }\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.