Recognitions of figures with two-dimensional cellular automata.
Résumé
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.
Nous considérons une famille de figures du plan discret 'rectangles, carrés, ellipses..); comment décider à l'aide d'un automate cellulaire plan, si une figure donnée appartient à la famille ? Nous donnons essentiellement trois types de résultats. Premièrement, nous cherchons un mode de définition de la famille de figures qui soit parallèle. Par exemple, un rectangle est une figure connexe sans trou telle que toute case du bord a exactement deux voisines dans le bord. Nous montrons que cette définition est équivalente à la définition classique dur rectangle et exhibons un automate cellulaire reconnaissant la famille des rectangles en temps optimal.
Deuxièmement, les figures sont définies par un algorithme facilement parallélisable et, un exemple naturel et très démonstratif est la reconnaissance des ellipses. Une ellipse est une figure avec deux cases distinguées (les foyers), formée de toutes les cases dont la somme des distances aux deux foyers ( pour la norme || ||1 or || ||) est inférieure à une constante k. Dans ce cas, algorithme de reconnaissance est le suivant : un signal engendré par un des deux foyers se diffuse à vitesses maximale dans toutes les directions du plan, puis est réfléchi par le bord de la figure. La figure est une ellipse si et seulement si tous ces signaux se résorbent,et sur l'autre foyer.
Pour finir, nous présentons un algorithme inspiré d'un algorithme de synchronisation de F. Grasselli pour reconnaitre la famille des carrés.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...