Gabriel graphs in arbitrary metric space and their cellular automaton for many grids - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue ACM Transactions on Autonomous and Adaptive Systems Année : 2010

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

Résumé

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.
Fichier non déposé

Dates et versions

inria-00541141 , version 1 (29-11-2010)

Identifiants

Citer

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, 2010, Special Issue on Spatial Computing, 6 (2), pp.1-14. ⟨10.1145/1968513.1968515⟩. ⟨inria-00541141⟩
156 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More