**Next:** Problem 57: Chromatic Number of the Plane

**Previous:** Problem 55: Pallet Loading

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

- Origin
Unknown.

- Status/Conjectures
Open.

- Motivation
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)

- Appearances
[BF01] conjecture the problem to be polynomially solvable.

- Categories
packing; optimization

- Entry Revision History
S. P. Fekete, 16 Jan. 2004; E. Demaine, 3 July 2009.

- [BF01]
C. Baur and S. P. Fekete. Approximation of geometric dispersion problems.

*Algorithmica*, 30:450–470, 2001.- [DEKIvO09]
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.- [FPT81]
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.- [HM85]
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.