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.
Solved: proved NP-hard by Abrahamsen and Stade [AS24].
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].
In 2024, Abrahamsen and Stade [AS24] proved that the problem is NP-hard, even when the polygon is an orthogonal and orthogonally convex polygon with half-integer coordinates.
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; J. Stade, 12 Dec. 2024.
Mikkel Abrahamsen and Jack Stade. Hardness of packing, covering and partitioning simple polygons with unit squares. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1355–1371, 2024.
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.