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(n^{2})-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(n^{2})-move reconfiguration
algorithm, improving their O(n^{3}) bound, as well as solving their
open problem about maintaining stricter connectivity.