Recognitions of figures with two-dimensional cellular automata.

Author :

Laboratoire de l'informatique du parallélisme Tougne, Laure

Abstract :

(eng) 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.

Subject :

2D Cellular Automata; Recognition; Family of Figures; Synchronization