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).
SILBOT, chirality
verifiedSilent oblivious particles cannot form a line if they share only chirality.
Assumed (added on the last edge are outlined)
Not assumed
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: chirality
- All particles agree on clockwise order, not on a common direction.
- 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: stays connected
- At every time the occupied nodes induce a connected subgraph.
Statement for this variant
The target shape is a line.
What is known
- a symmetric initial configuration
- a synchronous adversary
- holds even with common chirality
Results, in order of publication
No result recorded yet.
Open questions
Is line formation solvable in SILBOT when particles share just one direction instead of the full orientation 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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.