Mobility Matters
Home›Programmable matter›Self-organising particle systems›Shape formation in programmable matter

Shape formation in programmable matter

Particles must rearrange into a target shape (a line, a triangle, any shape built from triangles).

Problem statement and measuresexpand

From a connected initial configuration (the set of nodes occupied by particles) of \(n\) particles, the particles must reach a configuration forming a given target shape (at a scale depending on \(n\)). Time is in rounds; moves counts expansions and contractions.

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

no assumptions›oblivious, + common compass, + may disconnect

SILBOT, full orientation

verified
Time: unknownMoves: tight

With a common compass, silent oblivious particles form a line with \(O(n^2)\) moves, which is optimal.

Assumed (added on the last edge are outlined)

+Orientationfull common orientation (compass)+Connectivity during executionthe system may disconnect temporarily

Not assumed

Memoryoblivious, silent particles (SILBOT)Schedulerweak: non-atomic activations, an action may interleave with othersRandomnessdeterministicInitial shapeconnected, holes allowed
Formal definitions of this setting
Memory: oblivious
No persistent state and no messages; a particle decides from its view only.
Scheduler: weak scheduler
An activation's look, compute and move need not be atomic; concurrent activations may interfere. The scheduler of Bazzi and Briones is described as weak sequential, as non-atomic, and as fair asynchronous by different later papers Briones et al. 2023 Dufoulon et al. 2021 Chalopin et al. 2026.
Orientation: common compass
All particles agree on all six directions.
Randomness: deterministic
No random choices.
Initial shape: holes allowed
The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
Connectivity during execution: may disconnect
Connectivity is required only initially and at the end.

Statement for this variant

The target shape is a line.

What is known

Time · asynchronous rounds
unknown
No round bound recorded.
lower boundnone known
introductory—
current best—
Moves · total expansions and contractions (work)
tight
\(\Theta(n^2)\) moves.
lower bound
\(\Omega(n^2)\) Derakhshandeh et al. 2015
bottleneckdistance
holds when
  • Lemma 7: a compact start of diameter at most \(2\sqrt n+2\) must become a line
  • holds for any algorithm
introductory—
current best
\(O(n^2)\)
2-hop view

Results, in order of publication

Navarra & Piselli 2023 current best
Moves \(O(n^2)\)
2-hop view

Introductory and current best.

Navarra et al. 2025 also
Moves \(\text{finite}\)

Journal version; adds configurations with immovable obstacles, and scattering.

Open questions

  1. Does 1-hop visibility suffice for line formation in SILBOT Navarra & Piselli 2023?

  2. Which other shapes can SILBOT particles form Navarra & Piselli 2023?

Notes

The model is SILBOT D'Angelo et al. 2020: no memory, no messages, non-atomic asynchronous actions, view of two hops. The algorithm (WRain) disconnects the system temporarily. Checked against the full text of Navarra & Piselli 2023.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

SILBOT, chirality

Lower bounds from stronger settings hold here

No catalogued stronger setting.

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