Граф Габриэля

Граф Габриэля (Gabriel graph) множества $S$ точек двумерного пространства выражает понятие близости этих точек. Формально, это --- граф $G$ с множеством вершин $S$, в котором любые две различные точки $p,q\in S$ смежны, если замкнутый круг с отрезком $\overline{pq}$ в качестве диаметра не содержит других элементов множества $S$.

Графы Габриэля естественным образом обобщаются на пространства более высоких размерностей заменой кругов на шары. Названы в честь К.Р.Габриэля (K.R. Gabriel), который их ввёл в 1969.

Граф Габриэля является подграфом триангуляции Делоне и может быть найден за линейное время, если триангуляция Делоне задана. Он содержит в качестве подграфов евклидово минимальное остовное дерево, граф относительных окрестностей и граф ближайших соседей.