A 1D cellular automaton that moves particles until regular spatial placement
Résumé
We consider a finite cellular automaton with particles where each site can host at most one particle. Starting from an arbitrary initial configuration, our goal is to move the particles between neighbor sites until the distance to the nearest particle is minimized globally. Such a configuration corresponds in fact to a regular placement. This problem is a cellular automata equivalent of load-balancing in parallel computing, where each task is a particle and each processor a connected set of sites. We present a cellular automata rule that solves this problem in the 1D case, and is convergent, i.e. once the regular placement is achieved, the configuration does not change anymore. The rule is inspired from the Lloyd algorithm, computing a centroidal Voronoi tessellation. The dynamic of the rule is described at a higher level, using self-explanatory space-time diagrams. They exhibit signals acting as quantity of movement carrying the energy of system. Each signal bounces or pass through particles, causing their movement, until it eventually reaches the border and vanishes. When signals have all vanished, particles are regularly placed.