Gabriel graphs in arbitrary metric space and their cellular automaton for many grids

International audienceGabriel Graphs are subgraphs of Delaunay graphs that are used in many domains such as sensor networks and computer graphics. Although very useful in its original form, their definition is bounded to applications involving Euclidean spaces only, but their principles seem to be applicable to a wider range of applications. In this paper, we generalize this construct and define Metric Gabriel Graphs that transport the principles of Gabriel graphs on arbitrary metric space, allowing their use in domains like cellular automata and amorphous computing, or any other domains where a non-Euclidean metric is used. We study global/local properties of metric Gabriel graphs and use them to design a cellular automaton that draws the metric Gabriel graph of its input. This cellular automaton only uses 7 states to achieve this goal and has been tested on hexagonal grids, 4-connected and 8-connected square grids