Home›Programmable matter›Self-organising particle systems›Scattering of particles

Scattering of particles

Particles must reach a configuration in which no two particles occupy neighbouring nodes.

Problem statement and measurescollapse

Scattering: from a configuration of contracted particles, here a compact triangle, the particles must reach a configuration in which no two occupy neighbouring nodes, and stop. Shown is an illustrative run of event-driven activation: a particle can be activated only while it has a neighbour (blue); an activated particle (outlined) steps, by an expansion and a contraction, to a free node with fewer neighbours; the exact local rule of Navarra et al. 2025 is not reproduced here. Isolated particles (green) are never activated again.

From any initial configuration of \(n\) contracted particles (each occupying one node of the triangular lattice), the particles must reach a configuration in which no two occupy neighbouring nodes (a scattered configuration), and stop.

Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Picture people standing in a crowded square who must spread out until nobody is standing right next to anyone else. The floor is the triangular lattice: the endless graph whose nodes are the corners of a tiling of the plane by equal triangles; each node is joined by an edge to six others, its neighbours. A particle occupies one node and moves in two actions: an expansion into an empty neighbouring node, after which it occupies both, then a contraction into one of the two; so one expansion and one contraction move it by one node. There are \(n\) particles, each occupying one node at the start; the set of occupied nodes is the configuration. The particles are oblivious (they remember nothing from one action to the next) and silent (they send no messages); each decides only from what it sees around it. The goal is to reach a scattered configuration, where no two particles occupy neighbouring nodes, and then stop moving. The basic question is whether this is possible at all, from every starting configuration.

1AlgorithmActivated only when crowded SILBOT → Navarra et al. 2025

The catalogue has not read the full paper, so only its setting is described here. As reported by Navarra & Piselli 2023, Navarra, Prencipe, Bonini and Tracolli Navarra et al. 2025 let each particle see only its six neighbouring nodes, and use event-driven activation: a particle is activated (it gets a turn to act, an activation) as soon as it has a neighbour, and only then.

A particle with no neighbour is never activated, so it stays put.
A particle with a neighbour is activated, looks at which of its six neighbouring nodes are occupied, and decides from this view alone whether and where to move.
When no particle has a neighbour, no particle is activated again: the task is done and the particles have stopped.

Why it works and what it costs. Event-driven activation gives stopping for free: a scattered configuration is exactly one in which nobody is ever activated again. The difficulty is choosing the local rule so that crowded particles really do spread out instead of moving back and forth forever; the paper proves that its rule always succeeds in finite time. No time bound is recorded in the catalogue.

Why it matters. It shows how much the choice of scheduler can replace memory: with event-driven activation, particles without memory can tell when to stop.

2Lower boundA crowded hexagon must spread over three times its area SILBOT →

This simple counting argument is ours; the catalogue records no lower bound. In the triangular lattice every small triangle of three mutually neighbouring nodes can hold at most one particle of a scattered configuration. Counting triangles, a region with \(N\) nodes can hold at most about \(N/3\) scattered particles. Now start with the \(n\) particles packed into a full hexagon of radius \(r\) (it has about \(3r^2 = n\) nodes). The hexagon of radius \(1.5r\) around the same centre has about \(6.75r^2\) nodes, so it can hold only about \(2.25r^2 = 0.75n\) scattered particles.

Why it holds. So about \(n/4\) particles must end more than \(1.5r\) from the centre, having started within \(r\) of it: each travels at least \(r/2\), which is about \(\sqrt n\) nodes. That is at least about \(n\sqrt n\) moves in total, and, if the scheduler lets each particle act once per round (an interval of time in which every particle is activated at least once), about \(\sqrt n\) rounds. How close the known algorithm comes to these numbers is not recorded.

Why it matters. It shows that scattering, unlike gathering, forces the occupied region to grow in area, which costs real movement.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Moves

SILBOT standard

Silent oblivious particles scatter from any initial configuration.

unknown \(\text{finite}\) vs —

unknown — vs —

What the community started looking at

Scattering was posed for silent, oblivious particles, where the question is solvability without memory or messages Navarra et al. 2025.

Perspectives

From robots to particles Programmable matter re-asks the questions of robots in the plane on a lattice, with particles that touch, remember a little and stay connected; SILBOT takes memory and messages away again, and the stochastic approach replaces algorithms by a biased local rule.

All settings

The assumption tree (1 settings, 0 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Orientation › Randomness › Initial shape › Connectivity during execution.

tight near-optimal polynomial gap unknown impossible no variant

SILBOT standard setting draft Silent oblivious particles scatter from any initial configuration.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.