On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits

The paper looks at a problem in programmable matter where many small computational particles must “contain” a target shape using only their initial configuration—without moving—by finding the largest scaled version of the shape that fits. The authors note that while shape formation has been widely studied, shape containment has received less attention, and they suggest it could support tasks beyond formation, such as detecting structural flaws. They work within the geometric amoebot model and use a reconfigurable circuit extension to allow instantaneous transmission of simple signals across connected groups of particles. They prove a lower bound of Ω(√n) synchronous rounds for the general shape containment problem. They then focus on snowflake shapes and star-convex shapes, providing algorithms with runtimes of O(log^2 k) for star-convex shapes and O(√n log n) for snowflakes that are not star convex, where k is the maximum scale that can fit in the given structure.