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

where all the shapes that appear are necessarily convex, such as in a bumble bath,
etc. However, there are situations where the shapes are not convex, but we would
like to approximate it by a convex shape in order to make life easier. In this case,
we have an initial set of points, not necessarily convex, and we look for its convex
hull , i.e. the smallest convex set containing all the initial points. In the rest of this
chapter, these initial points will be called seeds . The question is how to compute the
convex hull of a set of seeds given as input.
A well known fact is that if there are finitely many seeds, their convex hull is a
polygon using these seeds as vertices and many classical algorithms exist to compute
this polygon as a list of vertices based on a set of seeds, everything being described
using a coordinate system. In contrast, this chapter considers the case where the
space is not the usual Euclidean space but a cellular space and the seeds are not
represented by coordinates but by a Boolean information holded by each cell and
representing whether the cell is a seed or not. So we do not assume any knowledge
of the classical algorithms but let us add a few words on why finite sets of seeds
have a polygonal convex hull in 2D Euclidean spaces.
The reason is the following: for the set of seeds to be convex, all the segments
joining them have to be in the set, so we consider now a set containing the seeds and
their pairwise segments. This new set in still not convex in general and we still need
to add all the segments joining the newly added points, and so on until no segment
is missing. The final result of this iterative adding process is indeed the minimal
convex set containing the seeds since only absolutely required segments have been
added. But all these additional points are strictly between the firstly added segments,
so the border of the convex hull is made of some of the firstly added segment with
the seeds as vertices. This is a very basic process, but it worths taking the time to
visualize it and to keep it in mind from the start.
In the context of cellular automata, the famous majority and voting rules and
some of their variations exhibit behaviors related to Euclidean convex hulls as de-
scribed in [7]. For instance, let us consider the majority rule where cells have two
states, either selected or not selected, and the rule selects a cell if at least 4 or its
neighbors are selected. If we denote by P the set of seeds and by the predicate
majo t ( the fact that the cell x is selected at time t by the rule majo, this behavior

can be written formally as:

x )

majo t + 1 ( x )= x ∈ P ∨ card { y ∈ N ( x ) | majo t ( y ) }≥ 4 (10.1)

Figure 10.2 shows an evolution of this rule with a dense set of seeds as initial con-
figuration. Here, the Moore neighborhood is used, so each cell has 8 neighbors, and
the number 4 is 50% of the neighborhood, hence the name of the rule. So the num-
ber would be 2 for a Von Neumann neighborhood, 3 for hexagonal cells which have
6 neighbors, and so on. In all these cases, it is clear that the final result is visually
related to Euclidean convex hulls. To make this precise, different approaches have
been tried. The goal is not only to understand what sort of convex hull is computed
by the majority rule, but also to be able to compute such a convex hull for arbitrary
sets of seeds, which is unfortunately not the case for the majority rule.