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-complete for polygons with holes [FPT81], even if the polygon is an orthogonal polygon with all coordinates being multiples of 1/2.

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.

Bibliography

BF01

C. Baur and S. P. Fekete.
Approximation of geometric dispersion problems.
Algorithmica, 30:450-470, 2001.

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.