Graphe de Gabriel
vignette|Graphe de Gabriel avec 100 points aléatoires Un graphe de Gabriel est un graphe qui connecte un ensemble de points dans un plan euclidien. Étant donné un ensemble de points dans un plan, deux points et de sont connectés par une arête dans le graphe de Gabriel de si et seulement si le disque ayant le segment comme diamètre ne contient aucun autre point de . De façon plus générale, en dimension quelconque, le graphe de Gabriel connecte n'importe quelle paire de points formant les extrémités du diamètre d'une sphère vide. Les graphes de Gabriel sont nommés ainsi d'après K. R. Gabriel, qui les a introduits dans un article avec en 1969. Le graphe de Gabriel de est un sous-graphe de la triangulation de Delaunay de . Il peut être calculé en un temps linéaire si la triangulation de Delaunay est connue (Matula et Sokal, 1980). Le graphe de Gabriel a pour sous-graphes les arbres couvrants minimums et le graphe des plus proches voisins. K. R. Gabriel et R. R. Sokal, « A new statistical approach to geographic variation analysis », Systematic Zoology, vol. 18, 1969, D. W. Matula et R. R. Sokal, « Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane », Geogr. Anal., vol.
