Problem 56: Packing Unit Squares in a Simple Polygon

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.

Bibliography

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