Skip to Main content Skip to Navigation
Journal articles

A 1D cellular automaton that moves particles until regular spatial placement

Luidnel Maignan 1, * Frédéric Gruau 1, 2 
* Corresponding author
1 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, LRI - Laboratoire de Recherche en Informatique
Abstract : 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.
Complete list of metadata
Contributor : Frederic Gruau Connect in order to contact the contributor
Submitted on : Monday, November 29, 2010 - 10:56:57 PM
Last modification on : Friday, August 5, 2022 - 10:47:31 AM


  • HAL Id : inria-00541142, version 1


Luidnel Maignan, Frédéric Gruau. A 1D cellular automaton that moves particles until regular spatial placement. Parallel Processing Letters, World Scientific Publishing, 2009, 19 (2), pp.315--331. ⟨inria-00541142⟩



Record views