가브리엘 그래프(Gabriel graph)는 유클리드 평면상의 점들 간의 근접성을 표현하는 그래프입니다.

알고리즘

1. 점 집합의 델로네 삼각분할(Delaunay & Urquhart )을 계산합니다.
   • O(n log n) 시간 복잡도
2. 델로네 삼각분할의 각 엣지에 대하여 다음과 같은 계산을 거칩니다.

   • 엣지의 두 끝 포인트를 지름으로 하는 원을 생성합니다.

   • 원 내부에 다른 포인트가 있는지 확인합니다.

     

   • 원 내부에 다른 포인트가 있으면 해당 엣지를 제거합니다.