19 novembre 2012

Luidnel MAIGNAN (LACL) salle des thèses

In this presentation, we study the programming of cellular automata and consider three problems of geometrical nature: moving “computation particles” on the grid in order to uniformize their density, constructing their convex hull, and constructing a connected proximity graph between them. With a focus on the algorithmic methodology, we show how to solve these problems using the same building blocks: computation of distances fields and motions/detections based on distance patterns. The obtained solutions use constant memory per cell and generalize over arbitrary regular grid. This shows that the algorithmic notion of modularity, but not only, can be retrieved in the context of cellular automata programming.