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

a Each point b Each line c Each diagonal d Subcase of (c)

Fig. 10.16 Hexagonal and square grid: the Gabriel graph is not connected. Grey seeds show
one of the connected components and gray balls give the reason of the non-connectedness.

of metric Gabriel graph is obtained: its vertices are the seeds as before, and two
seeds x and y have an edge connecting them if and only if there is a ball such that the
seeds contained in this ball can be partitioned in two sets X and Y with x

∈ X , y ∈ Y

2 r , r being the radius of the ball 2 . As before, such a ball if called a
metric Gabriel ball and its center a metric Gabriel center .
Compared to the original definition of Gabriel graphs, this definition deals with
the non-uniqueness of diameters by replacing the requirement of having two seeds
x and y such that d

and d ( X , Y )=

( x , y )= 2 r (this means precisely that [ xy ] is a diameter) by the

requirement of having two sets of seeds X and Y such that d 2 r . The non-

uniqueness of balls for a given diameter is managed by requiring only the existence
of at least one metric Gabriel ball. This means that whenever diameters and balls
are unique, this definition is equivalent with the original one, as it is the case for Eu-
clidean spaces. In fact, metric Gabriel graphs correspond exactly to original Gabriel
graphs when the distance function is the Euclidean one. Moreover, metric Gabriel
graphs are always connected for any set of points in any arbitrary metric space.
So this corresponds exactly to what we want to construct with our detection of
middles. More precisely, metric Gabriel centers are precisely the detectable middles.
To detect them, we use a very useful relation between metric Gabriel graphs and
distance fields: in the same way a ball of radius r is a metric Gabriel ball when the
set of seeds that it contains can be separated in two sets of distance 2 r , a distance
field neighborhood of radius r corresponds to that of a detectable middle when its
set of minimally valued cells can be separated in two sets of distance 2 r . This does
not hold in arbitrary metric spaces but is true in cellular spaces.
Figures 10.17a and 10.17b give an example of this correspondence in the case of
an hexagonal cellular space with three seeds.
In Fig. 10.17a, the first configuration shows a cell, indicated with a little dot, that
is the center of a metric Gabriel ball. Indeed, the two seeds that it contains forms
a diameter, which can be checked by exhibiting a shortest path joining them and
passing through the center, or simply by checking that they have distance 8, while
the ball is of radius 4. When considering only the neighborhood of this cell, in the
second configuration, the only available information is the distance values computed

( X , Y )=

2

Another way to put it is that there is an edge between two seeds x and y if and only if there
is a ball such that x and y are at distance 2 r and any other seed inside the ball is at distance
2 r from x or from y .