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: For systems of n congruent unlabeled disks in the translation model, Abellanas et al. showed that 2n-1 moves always suffice and 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, and thereby give a partial answer to one of their open problems.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.We also show that the reconfiguration problem with congruent disks in the sliding model is NP-hard, in both the labeled and unlabeled variants.For the reconfiguration with translations of n arbitrary labeled convex bodies in the plane, 2n moves are always sufficient and sometimes necessary.