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

Fig. 10.2 Convergence to one global convex hull

We first describe the early angular point of view to this problem, describing the
obtained convex hull in terms of Euclidean convexity with a restriction on the al-
lowed angles in Sect. 10.3. This point of view takes into account the Euclidean
positions of the cells. In Sect. 10.4 and Sect. 10.5, we then describe a more general
approach describing everything in terms of shortest paths, i.e. in terms of distances,
i.e. in terms of metric space. In this case, the focus is on something more intrinsic
than the cells position, namely the graph of communication of the cells. We then
conclude in Sect. 10.6 by a summary the complete cellular automaton that works
for any set of seeds and for any cellular space.

10.3 The Angular Point of View

The first approach is to consider the positions of the cells in Euclidean space. If
we take an arbitrary cell and consider the vector leading to each of its 8 neigh-
bors, we can see that they match the directions of the sides of the convex polygon
obtained in Fig. 10.2. This idea can be extended to Von Neumann neighborhood
with 4 vectors, and to hexagonal cellular spaces with 6 vectors. The trick is there-
fore to change the definition of convexity and to allow a set to be called convex if
and only if it is Euclidean convex polygon and its sides follow one the admitted