En géométrie algorithmique, le graphe de voisinage relatif (en anglais , 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 et si et seulement s'il n'existe pas de troisième point qui soit plus proche de et de qu'ils ne le sont entre eux. Il est introduit en 1980 par ..
Définition Le graphe de voisinage relatif d'un nuage de points a pour arêtes où est la distance euclidienne.
Algorithmes Supowit montre en 1983 que le graphe de voisinage relatif dans le plan euclidien peut être calculé en .. Il peut également être calculé en à partir de la triangulation de Delaunay..
Plus généralement, dans un espace de dimension , il peut être calculé en . Il est également possible de le calculer avec un algorithme probabiliste avec une complexité en moyenne en ..
Relations avec d'autres graphes
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.
Notes et références
Catégorie:Graphe géométrique Catégorie:Géométrie algorithmique