Convex Hulls and Metric Gabriel Graphs - Cellular Automata in Image Processing and Geometry - page 192

10.5.1.3 Gabriel Graphs and Middle Detection

In fact, since we detect the edges from their middles and theses middles are detected
from special distances patterns on the Voronoï diagram. This means that any edge
whose middle is not on the Voronoï diagram is not constructed. Removing those
non-detectable edges from Fig. 10.14b reduces it to Fig. 10.14c, and it comes out
that this resulting graph is also of great interest in applications relying on graphs in
Euclidean spaces: it is the Gabriel graph of our seeds. While edges of the Delaunay
graphs connect seeds of adjacent Voronoï region, the Gabriel graph retains only
edges that do not pass through the Voronoï region of another seed. This can be put
in another way which is the most known definition of this construction: there is an
edge between two seeds x and y if and only if there is a disc using the segment ]

as diameter and this disc does not contain any other seed. Given two seeds, such a
disc is called the Gabriel disc of these seeds and its center is called the Gabriel
center between these seeds. These Gabriel centers are exactly the middles that are
detected in Fig. 10.13, which makes Gabriel graphs very important for our purpose.
Gabriel graphs are proximity graphs introduced in [6] to study sets of geograph-
ical points. They are now used in many domains such as wireless [8] and sensors
networks for routing and communication management purpose. They also serve as
tools to study proximity of points in order to cluster them, in domains like data min-
ing, data and multivariate analysis [2], and machine learning [4, 12]. In computer
graphics [9, 13], they can help to convert a set of points into a 3D surfaces and to
obtain information about such surfaces. Their wide spread use is due to their numer-
ous properties. Indeed, they are related to Voronoï diagrams, Delaunay graphs as just
seen, but also to planar graphs, minimum spanning trees, nearest neighbor graphs,
and represent or contain optimal solutions for some classes of energy-minimizing
problem [8].
One particularly important property of Gabriel graphs is that they are always con-
nected . This is exactly the property what we need to ensure that the construction of
the convex hull is always complete, but for the cellular case. So our goal in the next
section is to see how this Euclidean construction fits to cellular spaces. In fact, some
adaptation will be required. So we will describe a new generalization of Gabriel
graphs that we call metric Gabriel graphs . The latter carries properties of Gabriel
graphs in any metric space, which allows them to be used in most considered cellu-
lar spaces in particular. This will provide us with the rule for the detection of middle
that we need in general for many cellular spaces.

[ xy

10.5.2 (Metric) Gabriel Graphs in Cellular Spaces

10.5.2.1 Failure of the Original Definition

In this section, we show that the original Gabriel graph definition does not accom-
modate the particularities of the cellular space. We highlight the fact that the orig-
inal definition relies on many uniqueness properties of the Euclidean space, the
uniqueness of the segment linking two points for example. Cellular spaces do not