Efficient Reconfiguration of Pivoting Tiles

Nadia Benbernou

This paper presents a general algorithmic framework for reconfiguring a modular robot consisting of identical 2D tiles, where the basic move is to pivot one tile around another at a shared vertex. The robot must remain connected and avoid collisions throughout all moves. For square tiles, and hexagonal tiles on either a triangular or hexagonal lattice, we obtain optimal O(n2)-move reconfiguration algorithms. In particular, we newly establish universal reconfigurability in the first two cases, and generalize a previous result for the third case from the robotics community (WAFR 2000).

For triangular tiles, reconfigurability is more difficult to characterize. We also consider a strengthening of a model analyzed by Dumitrescu and Pach (SoCG 2004) where tiles slide instead of pivot (making it easier to avoid collisions), and obtain an optimal O(n2)-move reconfiguration algorithm, improving their O(n3) bound, as well as solving their open problem about maintaining stricter connectivity.