Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares

Abstract

Edge-connected configurations of square modules, which can reconfigure through so-called sliding moves, are a well-established theoretical model for modular robots in two dimensions. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one such configuration of n squares into any other using O(n2) sliding moves, while maintaining connectivity. For certain pairs of configurations, reconfiguration may require Ω(n2) sliding moves. However, significantly fewer moves may be sufficient. We present Gather&Compact, an input-sensitive in-place algorithm that requires only O(Pn) sliding moves to transform one configuration into the other, where ̄P is the maximum perimeter of the two bounding boxes. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally make it xy-monotone. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin.