Anchored Rectangle and Square Packings

For points p1,ldots , pn in the unit square [0,1]2, an anchored rectangle packing consists of interior-disjoint axis-aligned empty rectangles r1,ldots , rnsubseteq [0,1]2 such that point pi is a corner of the rectangle ri (that is, ri is anchored at pi) for i=1,ldots, n. We show that for every set of n points in [0,1]2, there is an anchored rectangle packing of area at least 7/12-O(1/n), and for every n∈ N, there are point sets for which the area of every anchored rectangle packing is at most 2/3. The maximum area of an anchored square packing is always at least 5/32 and sometimes at most 7/27. The above constructive lower bounds immediately yield constant-factor approximations, of 7/12 -varepsilon for rectangles and 5/32 for squares, for computing anchored packings of maximum area in O(nlog n) time. We prove that a simple greedy strategy achieves a 9/47-approximation for anchored square packings, and 1/3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored rectangle and square packings in nO(1/varepsilon) and exp(rm poly(log (n/varepsilon))) time, respectively.