6
$\begingroup$

It is know that the Gabriel graph of a point set $P \subset \mathbb{R}^2$, $\mathcal{GG}(P)$ is a subset of the corresponding Delauney graph $\mathcal{DG}(P)$, i.e. $\mathcal{GG}(P) \subseteq\mathcal{DG}(P)$.

A Gabriel graph is defined as:

The Gabriel graph $\mathcal{GG}(P)$ of a point set $P \subset \mathbb{R}^2$ is defined as follows. The vertex set is $P$ and two vertices $p, q$ in $P$ are connected by an edge if and only if the interior of the disk with diameter $\overline{pq}$ is empty and $p, q$ are the only two points on its boundary. In particular, this implies that $\overline{pq}$ is also an edge in the Delaunay graph of P.

However, I am struggling to visualize or understand in what cases an edge $(p, q)$ would be in $\mathcal{DG}(P)$ but not in $\mathcal{GG}(P)$. Could someone give me an example? It seems to me as, by the empty-circle property of Voronoi edges, and their duality with the Delaunay graph, every edge in the Delaunay graph should satisfy the definition of a Gabriel graph. It is obvious that I am missing some edge case.

$\endgroup$
1
  • 2
    $\begingroup$ Note that the smallest disk containing a triangle and the smallest disk containing an edge of this triangle are, in general, not the same. Draw a triangle, all the disks for the Gabriel graph and the disk for the Delaunay graph. Can you place a point that does not destroy the Delaunay edge, but does destroy the Gabriel edge? $\endgroup$
    – Discrete lizard
    Commented Dec 27, 2021 at 13:05

2 Answers 2

2
$\begingroup$

From my answer to a similar question:

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.

$\endgroup$
6
$\begingroup$

Ah, I think I figured it out, thanks to the help from Discrete Lizard.

See the following image of a Delaunay triangulation, where I've highlighted one example where the edges would be included in DT, but not GG.

A Delauney triangulation where one of the points is highlighted, as it would not be included in a Gabriel graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.