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).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Moves
Deterministic, simply connected start, no chirality + strong scheduler, + no holes
0 open · 1 results
unknown
\(O(n^2)\) vs —
tight
\(O(n^2)\) vs \(\Omega(n^2)\)
distance
Universal shapes, sequential, randomized + sequential, + chirality, + randomized, + no holes
0 open · 1 results
tight
\(O(\sqrt n)\) vs \(\Omega(\sqrt n)\)
distance
unknown
— vs —
impossible
— vs \(\text{impossible}\)
symmetry breaking
impossible
— vs —
unknown
— vs —
tight
\(O(n^2)\) vs \(\Omega(n^2)\)
distance
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.