Graphe de Gabriel

Un graphe de Gabriel est un graphe qui connecte un ensemble de points dans un plan euclidien. Étant donné un ensemble $S$ de points dans un plan, deux points $P$ et $Q$ de $S$ sont connectés par une arête dans le graphe de Gabriel de $S$ si et seulement si le disque ayant le segment $[PQ]$ comme diamètre ne contient aucun autre point de $S$. 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 Robert R. Sokal (en) en 1969.

Graphe de Gabriel avec 100 points aléatoires

Le graphe de Gabriel de $S$ est un sous-graphe de la triangulation de Delaunay de $S$. 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, le graphe de voisinage relatif et le graphe des plus proches voisins.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Gabriel graph » (voir la liste des auteurs).
• (en) K. R. Gabriel et R. R. Sokal, « A new statistical approach to geographic variation analysis », Systematic Zoology, vol. 18, 1969, p. 259-270 DOI 10.2307/2412323
• (en) 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. 12, 1980, p. 205-222