The 2x2 simple packing problem

Andre van Renssen

We study the 2x2 simple packing problem: given a simple rectilinear grid polygon P consisting of n edges, we want to know the maximum number of non-overlapping, axis-aligned 2x2 squares we can pack in P. Fractional placement of the squares is not allowed. When P contains holes, the problem has been proven to be NP-complete. Whether the 2x2 simple packing problem can be solved in polynomial time or is NP-hard is a major open question in the area of packing problems.

We consider a number of techniques to solve this problem, including a transformation to a well-known graph problem: the Maximum Independent Set Problem. In general graphs this problem is NP-complete. But with the specific graphs we use (the intersection graph of all possible squares that can be placed in the polygon), a number of classes of polygons can be solved using this method. The graphs we construct to solve the packing problem, however, can be very large: their number of vertices is proportional to the number of squares of the optimal solution of the Maximum Independent Set Problem.

Using the results obtained from the graph, we describe specific configurations of edges in the polygon that always give rise to the same number of squares in the optimal solution. We describe a simple algorithm that uses these configurations to solve certain classes of polygons in O(n^2) time.