Maximum Area Axis-Aligned Square Packings

Given a point set S=s1,ldots , sn in the unit square U=[0,1]2, an anchored square packing is a set of n interior-disjoint empty squares in U such that si is a corner of the ith square. The reach R(S) of S is the set of points that may be covered by such a packing, that is, the union of all empty squares anchored at points in S. It is shown that area(R(S))≥ frac12 for every finite set Ssubset U, and this bound is the best possible. The region R(S) can be computed in O(nlog n) time. Finally, we prove that finding a maximum area anchored square packing is NP-complete. This is the first hardness proof for a geometric packing problem where the size of geometric objects in the packing is unrestricted.