Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements

The paper studies how a group of small robots (“amoebots”) that occupy grid nodes can change shape through expansion and contraction operations. It focuses on a “joint movement” extension where multiple amoebots can move in parallel to coordinate larger substructures. The authors examine centralized reconfiguration algorithms for geometric amoebot structures, aiming to reconfigure any structure from one class into some structure in another class. They specifically target sublinear-time algorithms. They answer an open question by proving that any structure can be reconfigured into a canonical line-segment structure in O(√n log n) rounds, without relying on extra assumptions used in prior work. They also provide a constant-time method to reconfigure any spiral structure into a line segment, enabled by new constant-time movement primitives.