论文标题
（重新）将平等磁盘包装到矩形中
(Re)packing Equal Disks into Rectangle
论文作者
论文摘要
将平等磁盘（或圆形）包装到矩形中的问题是一个基本的几何问题。 （通过这里的包装，我们是指矩形中的磁盘排列而没有重叠。）我们考虑以下相等磁盘包装问题的算法概括。在此问题中，对于给定的均等磁盘填充到矩形中的问题是，问题是是否通过更改少量磁盘的位置，我们可以为包装更多磁盘分配空间。更正式地，在重新包装问题中，对于给定的$ n $相等磁盘包装到矩形和整数$ k $和$ h $的情况下，我们询问是否可以通过更改最多的$ h $磁盘的位置，以打包$ n+k $磁盘。因此，包装相等磁盘的问题是我们问题的特殊情况，$ n = h = 0 $。 虽然将相等磁盘的计算复杂性保持在矩形中，但我们证明重新包装问题已经为$ h = 0 $。我们的主要算法贡献是一种算法，该算法在时间$ $（H+K）^{O（H+K）} \ CDOT | I | i |^{O（1）} $中解决重新包装问题，其中$ i $是输入大小。也就是说，问题是固定参数可通过$ k $和$ h $进行参数的处理。
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 $n$ equal disks packed into a rectangle and integers $k$ and $h$, we ask whether it is possible by changing positions of at most $h$ disks to pack $n+k$ disks. Thus the problem of packing equal disks is the special case of our problem with $n=h=0$. While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for $h=0$. Our main algorithmic contribution is an algorithm that solves the repacking problem in time $(h+k)^{O(h+k)}\cdot |I|^{O(1)}$, where $I$ is the input size. That is, the problem is fixed-parameter tractable parameterized by $k$ and $h$.
