Summary: We consider a discrete system of \(n\) devices lying on a 2-dimensional square grid and forming an initial connected shape \(S_I\). Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step. We study the problem of transforming \(S_I\) into a given connected target shape \(S_F\) of the same number of devices, via a finite sequence of line moves. Our focus is on designing centralised transformations aiming at minimising the total number of moves subject to the constraint of preserving connectivity of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the associated graphs of \(S_I\) and \(S_F\) are isomorphic to a Hamiltonian line. In particular, our transformations make \(O(n\log n)\) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving universal transformation that can transform any initial connected shape \(S_I\) into any target connected shape \(S_F\), through a sequence of \(O(n\sqrt{n})\) moves.
For the entire collection see [Zbl 1464.68019].