Points, distances, et automates cellulaires : algorithmique géométrique et spatiale
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
Spatial computing aims at providing a scalable framework where computation is distributed on a uniform computing medium and communication happen locally between nearest neighbors. We study the particular framework of cellular automata, using a regular grid and synchronous update. We propose to develop primitives allowing to structure the medium around a set of particles. We consider three problems of geometrical nature: moving the particles on the grid in order to uniformize the density, constructing their convex hull, constructing a connected proximity graph establishing connection between nearest particles. The last two problems are considered for multidimensional grid while uniformization is solved specifically for the one dimensional grid. The work approach is to consider the metric space underlying the cellular automata topology and construct generic mathematical object based solely on this metric. As a result, the algorithms derived from the properties of those objects, generalize over arbitrary regular grid. We implemented the usual ones, including hexagonal, 4 neighbors, and 8 neighbors square grid. All the solutions are based on the same basic component: the distance field, which associates to each site of the space its distance to the nearest particle. While the distance values are not bounded, it is shown that the difference between the values of neighboring sites is bounded, enabling encoding of the gradient into a finite state field. Our algorithms are expressed in terms of movements according to such gradient, and also detecting patterns in the gradient, and can thus be encoded in finite state of automata, using only a dozen of state.
Abstract FR:
Le calcul spatial a pour but de fournir un cadre de travail passant à l'échelle où les calculs sont distribués sur un milieu de calculs uniforme à communications locales. Nous étudions le cas particulier des automates cellulaires, utilisant une grille régulière et une communication synchrone. Nous proposons de développer des primitives permettant de structurer le milieu de calculs autour d'un ensemble de particules. Nous considérons trois problèmes géométriques : déplacer les particules afin d'uniformiser leur densité, construire leur enveloppe convex, et construire un graphe de proximité connexe connectant les plus proches particules entre elles. Ces deux derniers problèmes sont considérés sur grille multidimensionnelle, tandis que l'uniformisation est résolue sur un espace à une dimension. Notre approche est de considérer l'espace métrique correspondant à l'automate cellulaire et de construire des objets mathématiques basés sur cette métrique seule. Les algorithmes obtenues se généralisent ainsi vers des grilles arbitraires. Nous implantons les grilles usuelles : hexagonale et carré avec 4 et 8 voisins. Toutes les solutions sont basées sur la même brique de base : le champ de distances, associant à chaque point de l'espace sa distance à la plus proche particule. Alors que ces valeurs de distances ne sont pas bornées, nous utilisons le fait que la différence entre valeurs voisines l'est afin d'encoder les gradients sur un nombre fini d'états. Nos algorithmes, exprimés en terme de mouvement par rapport à ces gradients et de détection de motifs de gradient, s'encodent donc en automates d'états finis, avec un petit nombre d'états.