Convex Hulls on Cellular Spaces: Spatial Computing on Cellular Automata

In the cellular automata domain, the discrete convex hull computation rules proposed until now only deal with a connected set of seeds in infinite space, or with distant set of seeds in finite space. Taking a spatial computing point of view, we present a cellular automata rule that constructs the discrete convex hull of arbitrary set of seeds in infinite spaces. This is done by characterizing the cellular spaces and the convex hulls by metrical properties. The rule obtained is expressed using intrinsic and general properties of the cellular spaces, considering them as metric spaces. In particular, this rule is a direct application of metric Gabriel graphs. This allows the rule and its components to be used on all common 2D and 3D grids used in cellular automata.