next up previous
Next: Problem 57: Chromatic Number Up: The Open Problems Project Previous: Problem 55: Pallet Loading


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.


next up previous
Next: Problem 57: Chromatic Number Up: The Open Problems Project Previous: Problem 55: Pallet Loading
The Open Problems Project - December 08, 2012