Recognitions of figures with two-dimensional cellular automata.

Abstract : We consider a family of figures of the discrete plane (rectangles, squares, ellipses,...); how shall we decide with a 2D cellular automaton whether a given figure belongs to the family or not? We essentially give three kinds of results. First, we look for a parallel way of defining the family. For example, a rectangle is a connected figure without hole such that all cells that are in the border have exactly two neighbors in the border. We show that this definition is equivalent to the classical one and give a cellular automaton which recognizes the rectangles' family in an optimal time. Secondly, the figures are defined with the help of an algorithm which can be easily parallelized. A natural and meaningful example is the ellipses' recognition. An ellipse is a figure with two distinguished cells (the focuses); it is composed of all the cells the sum of distances to the two focus of which is less then a constant k. In this case, the algorithm of recognition is the following one: a signal, generated by one of the focuses, spreads with an optimal speed in all the possible directions, and it is reflected back by the border of the pattern. The figure is an ellipse if and only if all these signals are resorbed on the other focus. Finally, we present an other algorithm inspired by a synchronization algorithm due to F. Grasselli. in order to recognize the squares' family.
Document type :
Reports
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102119
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:14:46 AM
Last modification on : Wednesday, November 20, 2019 - 2:54:30 AM

File

RR1994-39.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102119, version 1

Collections

Citation

Laure Tougne. Recognitions of figures with two-dimensional cellular automata.. [Research Report] LIP RR-1994-39, Laboratoire de l'informatique du parallélisme. 1995, 2+85pp. ⟨hal-02102119⟩

Share

Metrics

Record views

9

Files downloads

12