Skip to Main content Skip to Navigation
Journal articles

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

Luidnel Maignan 1, * Frédéric Gruau 1, 2 
* Corresponding author
1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, LRI - Laboratoire de Recherche en Informatique
Abstract : Gabriel 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.
Complete list of metadata
Contributor : Frederic Gruau Connect in order to contact the contributor
Submitted on : Monday, November 29, 2010 - 10:50:32 PM
Last modification on : Friday, August 5, 2022 - 10:47:31 AM



Luidnel Maignan, Frédéric Gruau. Gabriel graphs in arbitrary metric space and their cellular automaton for many grids. ACM Transactions on Autonomous and Adaptive Systems, Association for Computing Machinery (ACM), 2010, Special Issue on Spatial Computing, 20 p. ⟨10.1145/1968513.1968515⟩. ⟨inria-00541141⟩



Record views