Un théorème d’accélération linéaire sur tout voisinage pour les automates cellulaires 2D

Dans cet exposé je présenterai un résultat récent obtenu en collaboration avec Anaël Grandjean qui permet d’obtenir une accélération linéaire de la reconnaissance d’images (motifs rectangulaires) par des automates cellulaires 2D fonctionnant sur des voisinages quelconques. Je présenterai d’abord les automates cellulaires, et la reconnaissance d’images, puis les résultats connus d’accélération linéaire sur les voisinages classiques: von Neumann (4 plus proches voisins) et Moore (8 plus proches voisins).

J’expliquerai les difficultés algorithmiques qui apparaissent lorsque l’on considère des voisinages quelconques, et les idées qui permettent de les résoudre.