Graphe des plus proches voisins

Graphe des plus proches voisins pour 100 points placés aléatoirement dans un carré.

En géométrie algorithmique, le graphe des plus proches voisins (en anglais nearest neighbor graph, souvent abrégé NNG) est un graphe orienté défini pour un ensemble de points dans un espace métrique. Il relit un point ${\displaystyle p}$ à un point ${\displaystyle q}$ si et seulement si ${\displaystyle q}$ est le plus proche voisin de ${\displaystyle p}$. Le graphe des plus proches voisins peut également être considéré comme un graphe non orienté en ignorant l'orientation des arêtes.

Propriétés

Dans le plan euclidien, le degré des sommets du graphe des plus proches voisins est au plus 6, et même au plus 5 si les points sont en position générale[1].

Dans un espace euclidien, le graphe des plus proches voisins, vu comme un graphe non orienté, est un sous-graphe de la triangulation de Delaunay, du graphe de Gabriel et du graphe de voisinage relatif. Si les points sont en position générale, il est un sous-graphe de l'arbre couvrant de poids minimum[1].

Notes et références

1. (en) D. Eppstein, M. S. Paterson et F. F. Yao, « On Nearest-Neighbor Graphs », Discrete & Computational Geometry, vol. 17, n^o 3,‎ 1^er avril 1997, p. 263–282 (ISSN 1432-0444, DOI 10.1007/PL00009293, lire en ligne, consulté le 25 février 2024)