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

Luidnel Maignan 1, * Frédéric Gruau 1, 2
* Auteur correspondant
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, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
2 HEP
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.
Type de document :
Article dans une revue
ACM Transactions on Autonomous and Adaptive Systems, Association for Computing Machinery (ACM), 2010, Special Issue on Spatial Computing, 20 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00541141
Contributeur : Frederic Gruau <>
Soumis le : lundi 29 novembre 2010 - 22:50:32
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Identifiants

  • HAL Id : inria-00541141, version 1

Collections

Citation

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. 〈inria-00541141〉

Partager

Métriques

Consultations de la notice

233