Abstract
We consider a discrete system of n devices lying on a 2-dimensional square grid and forming an initial connected shape SI. 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, called a line move. 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 contain a Hamiltonian path. 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 root n) moves. (C) 2021 Elsevier B.V. All rights reserved.