The Open Problems Project

Next: Problem 57: Chromatic Number of the Plane

Previous: Problem 55: Pallet Loading

Problem 56: Packing Unit Squares in a Simple Polygon


What is the complexity of deciding whether a given number of axis-parallel unit squares can be packed into a simple polygon (without holes)?






Natural packing problem.

Partial and Related Results

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].

Related Open Problems

What is the complexity of pallet loading? (Problem 55)


[BF01] conjecture the problem to be polynomially solvable.


packing; optimization

Entry Revision History

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.