Graphe de voisinage relatif
From Wikipedia, the free encyclopedia
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 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 Godfried Toussaint (en)[1].
Le graphe de voisinage relatif d'un nuage de points a pour arêtes où est la distance euclidienne.
