Sliding Disks in the Plane

摘要

Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk slides in the plane without intersecting any other disk, so that its center moves along an arbitrary (open) continuous curve. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii and disk placements. For example, with n congruent disks, 3n/2 +O((n log n)~(1/2) ) moves always suffice for transforming the start configuration into the target configuration; on the other hand, (1 + (1/15)) n — O(n~(1/2)) moves are sometimes necessary.