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

Chapter 10
Convex Hulls and Metric Gabriel Graphs

Luidnel Maignan and Frédéric Gruau

Abstract. The convex hulls construction is mostly known from the point of view
of 2D Euclidean geometry where it associates to a given set of points called seeds,
the smallest convex polygon containing these seeds. For the cellular automata case,
different adaptations of the definition and associated constructions have been pro-
posed to fit with the discreteness of the cellular spaces. We review some of these
propositions and show the link with the famous majority and voting rules. We then
unify all these definitions in a unique framework using metric spaces and provide
a general solution to the problem. This will lead us to an understanding of the con-
vex hull construction as a chase for shortest paths. This emphases the importance of
Voronoï diagrams and its related proximity graphs: Delaunay and Gabriel graphs.
Indeed, the central problem to be solved is that of connecting arbitrary sets of seeds,
in a local and finite-state way, while remaining inside the desired convex hull, i.e
by shortest paths. This is exactly what will be made possible by a suitable general-
ization of Gabriel graphs from Euclidean to arbitrary metric spaces and the study of
its construction by cellular automata. The general solution therefore consists of two
levels: a connecting level using the metric Gabriel graphs and a level completing
the convex hull locally as the majority rule does. Both levels can be generalized to
compute the convex hull, when the seeds are moving.

10.1 Notational and Naming Convention

In this chapter, the set of all cells of the space is denoted S . The neighborhood
of a cell x is denoted N

( x ) and does not include the cell x itself. A set of cells

Luidnel Maignan
LACL, Université Paris-Est Créteil, France
e-mail: [e-mail]
Frédéric Gruau
LRI, Université Paris-Sud Orsay, France
e-mail: [e-mail]