Shape formation in programmable matter: Universal shapes, sequential, randomized

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›+ sequential, + chirality, + randomized, + no holes

Universal shapes, sequential, randomized

verified

Time: tightMoves: unknown

Any shape made of a constant number of triangles, from a well-initialised start, in \(\Theta(\sqrt n)\) rounds.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Schedulersequential: one particle active at a time+Orientationcommon chirality+Randomnessrandomized+Initial shapesimply connected (no holes)

Not assumed

Connectivity 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: sequential: At most one particle is active at any time.
Orientation: chirality: All particles agree on clockwise order, not on a common direction.
Randomness: randomized: Particles flip fair coins; guarantees hold with high probability or in expectation.
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

tight

\(\Theta(\sqrt n)\).

lower bound

\(\Omega(\sqrt n)\) Derakhshandeh et al. 2016

bottleneckdistance

holds when

when the shape differs from the initial configuration

introductory—

current best

\(O(\sqrt n)\)

Derakhshandeh et al. 2016

well-initialised configuration

Moves · total expansions and contractions (work)

unknown

—

lower boundnone known

introductory—

current best—

Results, in order of publication

Derakhshandeh et al. 2016 current best

Time \(O(\sqrt n)\)

well-initialised configuration

Introductory and current best.

Open questions

None recorded for this variant.

Notes

The model assumptions (chirality, sequential activation, randomization) are as described by Di Luna et al. 2020.

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

Deterministic, simply connected start, no chirality

Time \(O(n^2)\)Moves \(O(n^2)\)

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.