Gabriel graph

In mathematics and computational geometry, the Gabriel graph of a set ${\displaystyle S}$ of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph ${\displaystyle G}$ with vertex set ${\displaystyle S}$ in which any two distinct points ${\displaystyle p\in S}$ and ${\displaystyle q\in S}$ are adjacent precisely when the closed disc having ${\displaystyle pq}$ as a diameter contains no other points. Another way of expressing the same adjacency criterion is that ${\displaystyle p}$ and ${\displaystyle q}$ should be the two closest given points to their midpoint, with no other given point being as close. Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. Ruben Gabriel, who introduced them in a paper with Robert R. Sokal in 1969.[1]

Points ${\displaystyle a}$ and ${\displaystyle b}$ are Gabriel neighbours, as ${\displaystyle c}$ is outside their diameter circle.

The presence of point ${\displaystyle c}$ within the circle prevents points ${\displaystyle a}$ and ${\displaystyle b}$ from being Gabriel neighbors.

The Gabriel graph of 100 random points