On reconfiguration of disks in the plane and related problems

We revisit two natural reconfiguration models for systems of disjoint objects in the plane: translation and sliding. Consider a set of n pairwise interior-disjoint objects in the plane that need to be brought from a given start (initial) configuration S into a desired goal (target) configuration T. without causing collisions. In the translation model, in one move an object is translated along a fixed direction to another position in the plane. In the sliding model, one move is sliding an object to another location in the plane by means of a continuous rigid motion (that could involve rotations). We obtain various combinatorial and computational results for these two models: (I) For systems of n congruent unlabeled disks in the translation model. Abellanas et al. showed that 2n - 1 moves always suffice and left perpendicular8n/5right perpendicular moves are sometimes necessary for transforming the start configuration into the target configuration. Here we further improve the lower bound to left perpendicular5n/3right perpendicular - 1, and thereby give a partial answer to one of their open problems. (II) We show that the reconfiguration problem with congruent disks in the translation model is NP-hard, in both the labeled and unlabeled variants. This answers another open problem of Abellanas et al. (III) We also show that the reconfiguration problem with congruent disks in the sliding model is NP-hard, in both the labeled and unlabeled variants. (IV) For the reconfiguration with translations of n arbitrary labeled convex bodies in the plane, 2n moves are always sufficient and sometimes necessary. (C) 2012 Elsevier B.V. All rights reserved.