Next: Problem 57: Chromatic Number of the Plane
Previous: Problem 55: Pallet Loading
What is the complexity of deciding whether a given number of axis-parallel unit squares can be packed into a simple polygon (without holes)?
Unknown.
Open.
Natural packing problem.
The problem is known to be NP-hard for polygons with holes [FPT81], even if the polygon is an orthogonal polygon with all coordinates being multiples of 1/2. Recently this version of the problem was shown to be in NP [DEKIvO09], making it NP-complete.
The problem is the decision version for two optimization problems of very different behavior. There is a PTAS for packing the maximum number of squares of fixed size [HM85]. Maximizing the size of squares such that a fixed number of squares can be packed has a lower bound on approximation of 14/13, and there is a 3/2-approximation [BF01].
What is the complexity of pallet loading? (Problem 55)
[BF01] conjecture the problem to be polynomially solvable.
packing; optimization
S. P. Fekete, 16 Jan. 2004; E. Demaine, 3 July 2009.
C. Baur and S. P. Fekete. Approximation of geometric dispersion problems. Algorithmica, 30:450–470, 2001.
Muriel Dulieu, Dania El-Khechen, John Iacono, and Nikolaj van Omme. Packing 2 \times 2 unit squares into grid polygons is NP-complete. In Proceedings of the 21st Canadian Conference on Computational Geometry, Vancouver, Canada, August 2009.
R. J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett., 12(3):133–137, 1981.
D. S. Hochbaum and W. Maas. Approximation schemes for covering and packing problems in image processing and VLSI. J. Assoc. Comput. Mach., 32:130–136, 1985.