Polynomial-time approximation schemes for circle and other packing problems (Q329299): Difference between revisions

This paper considers the problem of packing a set of circles of different radii into the minimum number of square bins of unit size. The related problem of packing a set of circles into a unit-width strip of minimum height is also considered. The algorithms presented in this work can be extended to other packing problems not involving circles, like packing regular polygons or \(d\)-dimensional spheres into unit-size bins. The algorithm for packing circles into unit-size square bins uses a partition technique that has previously been used on other packing problems. The set of circles is divided into three sets: big, medium, and small. The set of medium circles has a small total area so it is possible to pack them all in a small number of bins. An important consequence of removing the medium circles is that now there is a gap between the radius of the smallest big circle and the radius of the largest small circle. This allows the authors to deal with each type of circles independently. There is a number of technical challenges when packing circles that is not present when packing, for example, rectangles. Even if the circles have rational radii we cannot ensure that the position of the center of a circle inside a bin has rational coordinates. To ensure that there is a packing for the circles with centers at rational coordinates within the bins, the authors increase the height of each bin by a small amount \(\gamma\). Big circles are selected so that the radius of each big circle is at least a constant value \(\delta\), and so at most a constant number of big circles can be packed in a bin. A novel idea introduced in this paper for packing big circles inside a bin is to reduce the problem to that of solving a semi-algebraic system derived by the set of constraints that the centers of the circles need to satisfy to ensure that they do not overlap and they all fit in the bin. Finding a solution for this system can then be transformed into deciding the satisfiability of some algebraic formula. Any algorithm for the quantifier-elimination problem can then be used to decide the satisfiability of the above formula. A very nice consequence of this approach is that the time complexity of the algorithm is polynomial in \(1/\gamma\) and not exponential in \(1/\gamma\) as it would happen if an enumeration-based approach had been used. A grouping technique similar to that used by \textit{W. Fernandez de la Vega} and \textit{G. S. Lueker} [Combinatorica 1, 349--355 (1981; Zbl 0485.68057)] and \textit{C. Kenyon} and \textit{E. Rémila} [Math. Oper. Res. 25, No. 4, 645--656 (2000; Zbl 0977.90043)] is then used to pack all big squares into the same number of bins that would be used by an optimal solution on the original-size bins. A similar technique as that used by \textit{K. Jansen} and \textit{R. Solis-Oba} [in: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms, SODA'06. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 143--152 (2006; Zbl 1192.90176)] to pack squares is then used to divide the empty space left by the big circles into smaller rectangular sub-bins and the above algorithm is then recursively applied on the sub-bins to pack the small circles. The algorithm for packing circles into bins can then easily be transformed into one for packing circles into a strip of unit-width and near-optimum height.