The lifting model for reconfiguration
Sergey Bereg, Adrian Dumitrescu · 2005
Abstract Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in theplane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk is lifted from the plane and placed back in the plane atanother location, without intersecting any other disk. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. We then extend our results forarbitrary disks to systems of pseudodisks, in particular to sets of homothetic copies of a convex object. 1 Introduction Consider a set (system) of n pairwise disjoint objects in the plane that need to be brought from a givenstart (initial) configuration S into a desired goal (target) configuration T. The motion planning problemfor such a system is that of computing a sequence of object motions (schedule) that achieves this task. If