{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:16Z","timestamp":1750307296600,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,6,1]],"date-time":"2011-06-01T00:00:00Z","timestamp":1306886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p>Gabriel graphs are subgraphs of Delaunay graphs that are used in many domains such as sensor networks and computer graphics. Although very useful in their 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 article, 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 seven states to achieve this goal and has been tested on hexagonal grids, 4-connected, and 8-connected square grids.<\/jats:p>","DOI":"10.1145\/1968513.1968515","type":"journal-article","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T17:31:10Z","timestamp":1309282270000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Gabriel Graphs in Arbitrary Metric Space and their Cellular Automaton for Many Grids"],"prefix":"10.1145","volume":"6","author":[{"given":"Luidnel","family":"Maignan","sequence":"first","affiliation":[{"name":"INRIA Saclay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Gruau","sequence":"additional","affiliation":[{"name":"INRIA Saclay, LRI, LIRMM"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/332833.332842"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(96)00003-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2004.04.009"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2008.53"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02085-8_2"},{"key":"e_1_2_1_7_1","volume-title":"Intelligent Computing in Signal Processing and Pattern Recognition. Lecture Note in Control and Information Sciences","volume":"345","author":"Chen H.","unstructured":"Chen , H. and Wei , W . 2006. Geodesic Gabriel graph-based supervised nonlinear manifold learning . In Intelligent Computing in Signal Processing and Pattern Recognition. Lecture Note in Control and Information Sciences , Vol. 345 . Springer, Berlin, 882--887. Chen, H. and Wei, W. 2006. Geodesic Gabriel graph-based supervised nonlinear manifold learning. In Intelligent Computing in Signal Processing and Pattern Recognition. Lecture Note in Control and Information Sciences, Vol. 345. Springer, Berlin, 882--887."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Chopard B. and Droz M. 1998. Cellular Automata Modeling of Physical Systems. Cambridge University Press. Chopard B. and Droz M. 1998. Cellular Automata Modeling of Physical Systems. Cambridge University Press.","DOI":"10.1017\/CBO9780511549755"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Gross J. L. and Yellen J. 2003. Handbook of Graph Theory (Discrete Mathematics and Its Applications). CRC Press. Gross J. L. and Yellen J. 2003. Handbook of Graph Theory (Discrete Mathematics and Its Applications) . CRC Press.","DOI":"10.1201\/9780203490204"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2412323"},{"volume-title":"Proc. IEEE. 1502--1517","author":"Jaromczyk J. W.","key":"e_1_2_1_12_1","unstructured":"Jaromczyk , J. W. and Toussaint , G. T . 1992. Relative neighborhood graphs and their relatives . Proc. IEEE. 1502--1517 . Jaromczyk, J. W. and Toussaint, G. T. 1992. Relative neighborhood graphs and their relatives. Proc. IEEE. 1502--1517."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2008.132"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11751540_47"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SASOW.2008.52"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0895-7177(97)00145-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/544741.544839"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2006.02.008"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Toffoli T. and Margolus N. 1987. Cellular Automata Machines A New Environment for Modeling. The MIT Press Cambridge MA. Toffoli T. and Margolus N. 1987. Cellular Automata Machines A New Environment for Modeling . The MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/1763.001.0001"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1968513.1968515","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1968513.1968515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:48Z","timestamp":1750244388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1968513.1968515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.1145\/1968513.1968515"],"URL":"https:\/\/doi.org\/10.1145\/1968513.1968515","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2011,6]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}