Graphe des plus proches voisins — Wikipédia

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.

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].

• Portail de la géométrie
• Portail de l'informatique théorique