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−12n−1 moves always suffice and ⌊8n/5⌋⌊8n/5⌋ moves are sometimes necessary for transforming the start configuration into the target configuration. Here we further improve the lower bound to ⌊5n/3⌋−1⌊5n/3⌋−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.