Shape formation by hybrid programmable matter
One finite-automaton agent rearranges passive tiles into a target shape.
Problem statement and measuresexpand
\(n\) passive hexagonal tiles (rhombic dodecahedra in 3D) occupy nodes of a lattice and form a connected structure. A single active agent, a deterministic finite automaton, starts on a tile, must always stand on or next to a tile, sees its node and the adjacent nodes, and in each round lifts a tile, places the tile it carries, or moves to an adjacent node; it carries at most one tile, and the tiles (with the carried tile counted at the agent's node) must stay connected. It must rearrange the tiles into a target shape (a line, a triangle, or an intermediate structure such as a block or a tree). Time counts the agent's rounds.
Measures: Time, rounds; in each round the agent performs one Look-Compute-Move step.
Three-dimensional
verifiedIn 3D, one agent turns any connected tile structure into a low-diameter icicle in \(O(n^3)\) rounds.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Space: 3D
- Tiles occupy nodes of the face-centred cubic lattice; planar structures are a special case.
What is known
Results, in order of publication
Introductory and current best (Theorem 14); matches the prior runtime of 3D line formation.
Open questions
None recorded for this variant.
Notes
Checked against the full text.
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
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.