Show that Delaunay triangulation contains Gabriel graph

Question

Let $P \in \mathbb{R} \times \mathbb{R}$ be a set of points on a euclidean plane.

A Delaunay triangulation of $P$ is a graph $DT(P) = (P, E_{D})$ such that $\forall p, q, r \in P$, the edges $(p, q), (q, r), (r, p) \in E_{D}$ if no other point from $P$ is inside the circle passing through $p, q, r$.

A Gabriel graph of $P$ is a graph $GG(P) = (P, E_{G})$ such that $(p, q) \in E_{G} \iff $ the circle with the diamter $d(p, q)$ passing through $p, q$ contains no other point from $P$.

Prove that $\forall P \in \mathbb{R} \times \mathbb{R}, GG(P) \subset DT(P)$ so that $E_{G} \subset E_{D}$

Answer 1

Suppose that $P$ does not contain only points laying on a common line. For $p,q\in P$, define $r\in P$ such that $r\neq p,q$ and satisfies that $\min_{s\in P}(\text{radius of the circle passing through }p,q\text{ and }s)=$radius of the circle passing through $p,q$ and $r$. Under the Gabriel's condition, then this triplet works also for the definition of Delaunay.

Answer 2

There is another definition of the Delaunay triangulation, which is equivalent to one you mentioned. For example, this definition can be found in this paper:

Definition 1 (Delaunay Triangulation) Given a set $S$ of points in general position, the Delaunay triangulation $DT(S)$ of $S$ is the graph whose vertex set is $S$ and that has an edge between two vertices $x$ and $y$ if and only if there exists a closed disk $D$ such that: (1) $x$ and $y$ are on the boundary of $D$, and (2) $D \cap S \setminus \{x, y\} = \emptyset$.

It's easy to see that for each pair of vertices $x$ and $y$, connected by a Delaunay edge, centers of all the possible disks, satisfying the definition above, comprise a Voronoi segment (or ray), separating the pair of (probably infinite) polygonal regions, corresponding to sites $x$ and $y$.

Now, let's prove that any edge of the Gabriel graph is also an edge of the Delaunay graph. According to the Gabriel graph definition, for each edge $(x,y)$ of the Gabriel graph we can find an empty disk $D$ with a center at the midpoint of this edge and radius, equal to the half-length of this edge. Looking at the definition of the Delaunay graph above, we immediately notice that we've found a disk $D$, satisfying this definition - so this edge is also a Delaunay edge. This proves, that the Gabriel graph is a subgraph of the Delaunay graph.

A Delaunay edge $(x,y)$ won't be a Gabriel edge, if the set of all the possible empty disks with $x$ and $y$ on their boundaries doesn't contain the disk with minimum possible radius (which is the half-length of this edge). In other words, this will happen when the Delaunay edge $(x,y)$ doesn't intersect the segment (or ray), separating sites $x$ and $y$ in the Voronoi diagram.