Graphe des plus proches voisins

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 contient un arc du point ${\displaystyle p}$ vers un point ${\displaystyle q}$ si et seulement si ${\displaystyle q}$ est un 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.