Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach

The work considers a programmable matter system where many devices sit on a 2D grid and can perform a basic mechanical move: rotating around each other. The goal is to change one overall shape into another while keeping the system globally connected at every step. The authors focus on a specific family of shapes (“nice shapes”) defined by a central line, where every node either lies on that line or connects to it through a perpendicular line of nodes. They prove that adding a minimal 3-node seed allows a line of n nodes to be transformed into a nice shape with n−1 nodes. They further show that a 4-node seed can transform nice shapes of size n into any other nice shape of the same size, with a stated time bound of O(n^2). They note that extending the method to a broader class of shapes remains open.