(Re)packing Equal Disks into Rectangle.

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of equal disks packed into a rectangle and integers and , we ask whether it is possible by changing positions of at most disks to pack disks. Thus the problem of packing equal disks is the special case of our problem with . While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for . Our main algorithmic contribution is an algorithm that solves the repacking problem in time , where || is the input size. That is, the problem is fixed-parameter tractable parameterized by and .