# Anchored Rectangle and Square Packings

arXiv: https://arxiv.org/abs/1603.00060 · HTML: https://mlsanity.com/paper/1603.00060/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Feb 2016.

## Built on by (most cited first, 1 of 1)

- [Introducing Resizable Region Packing Problem in Image Generation, with a Heuristic Solution](https://mlsanity.com/paper/2509.16363/) (2025)

## Abstract (arXiv)

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.