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›+ constant memory›+ strong scheduler, + no holes

Deterministic, simply connected start, no chirality

standard settingverified
Time: unknownMoves: tight

Which shapes are deterministically formable from a simply connected start is characterised; \(O(n^2)\) rounds and moves, and the moves are optimal.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Schedulerstrong: atomic activations under a fair adversary+Initial shapesimply connected (no holes)

Not assumed

Orientationno common orientation and no chiralityRandomnessdeterministicConnectivity during executionthe system must stay connected
Formal definitions of this setting
Memory: constant memory
Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
Scheduler: strong scheduler
Each activation is executed atomically; the adversary chooses the order, fairly.
Orientation: no orientation
Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
Randomness: deterministic
No random choices.
Initial shape: no holes
The initial configuration is connected and encloses no empty node. Also called contractible Briones et al. 2023 or hole-free Gastineau et al. 2019.
Connectivity during execution: stays connected
At every time the occupied nodes induce a connected subgraph.

What is known

Time · asynchronous rounds
unknown
No time lower bound recorded.
lower boundnone known
introductory—
current best
\(O(n^2)\)
Moves · total expansions and contractions (work)
tight
\(\Theta(n^2)\) moves.
lower bound
\(\Omega(n^2)\) Di Luna et al. 2020
bottleneckdistance
holds when
  • some initial configurations and shapes
introductory—
current best
\(O(n^2)\)

Results, in order of publication

Di Luna et al. 2020 current best
Time \(O(n^2)\)Moves \(O(n^2)\)

Introductory for the deterministic, chirality-free setting and current best; "chirality is computationally irrelevant for shape formation"; with randomization any shape is formable for large \(n\).

Open questions

None recorded for this variant.

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

Universal shapes, sequential, randomized
Time \(\Omega(\sqrt n)\)

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