# Maximum Area Axis-Aligned Square Packings

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2018.

## 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)

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.