Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures

The paper studies how a single agent with limited sensing and finite computational power can rearrange passive tiles in 3D to form a target shape. The specific target is an “icicle,” defined as a dense, hole-free structure chosen because it is useful as an intermediate for further shape formation tasks. The authors design an algorithm that transforms any initially connected tile structure into an icicle. They analyze the algorithm’s step complexity as O(n^3), which they state matches the runtime of a prior line-formation algorithm. They also report extensive experiments showing that the method decreases the diameter of tile structures on average, and they highlight that the icicle shape offers advantages over a line shape, such as reduced diameter and multiple removable tiles.