# On Greedily Packing Anchored Rectangles

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

## Key facts

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

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

Consider a set P of points in the unit square U, one of them being the origin. For each point p in P you may draw a rectangle in U with its lower-left corner in p. What is the maximum area such rectangles can cover without overlapping each other? Freedman [1969] posed this problem in 1969, asking whether one can always cover at least 50% of U. Over 40 years later, Dumitrescu and T'oth [2011] achieved the first constant coverage of 9.1%; since then, no significant progress was made. While 9.1% might seem low, the authors could not find any instance where their algorithm covers less than 50%, nourishing the hope to eventually prove a 50% bound. While we indeed significantly raise the algorithm's coverage to 39%, we extinguish the hope of reaching 50% by giving points for which the coverage is below 43.3%. Our analysis studies the algorithm's average and worst-case density of so-called tiles, which represent the area where a given point can freely choose its maximum-area rectangle. Our approachis comparatively general and may potentially help in analyzing related algorithms.