In this paper, we study the main open question of [Michail, Skretas, Spirakis, ICALP'17], asking what are the families of two-dimensional geometric shapes, drawn on a square grid, that can be transformed into each other by a sequence of rotation operations, none of which disconnects the shape. The model represents programmable matter systems consisting of interconnected robotic modules that perform the minimal mechanical operation of 90° rotations around each other. The goal is to transform an initial connected shape of modules A into a target connected shape B . Under the necessary assumption that the two shapes have identical colour cardinalities on a checkered colouring of the grid, and using at most a constant number of auxiliary modules to trigger the transformation, we prove that almost any pair of such shapes can be transformed into each other within an optimal O ( n 2 ) rotation operations none of which disconnects the shape.

We study a model of programmable matter systems consisting of n devices lying on a 2-dimensional square grid which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape A into a target shape B. We investigate the class of shapes which can be constructed in such a scenario under the additional constraint of maintaining global connectivity at all times. We focus on the scenario of transforming nice shapes, a class of shapes consisting of a central line L where for all nodes u in S either u∈L or u is connected to L by a line of nodes perpendicular to L. We prove that by introducing a minimal 3-node seed it is possible for the canonical shape of a line of n nodes to be transformed into a nice shape of n−1 nodes. We use this to show that a 4-node seed enables the transformation of nice shapes of size n into any other nice shape of size n in O(n2) time. We leave as an open problem the expansion of the class of shapes which can be constructed using such a seed to include those derived from nice shapes.