On Packing Almost Half of a Square with Anchored Rectangles: A Constructive Approach

In this paper, we consider the following geometric puzzle whose origin was traced to Allan Freedman cite{croft91,tutte69} in the 1960s by Dumitrescu and T{o}th cite{adriancasaba2011}. The puzzle has been popularized of late by Peter Winkler cite{Winkler2007}. Let $P_{n}$ be a set of $n$ points, including the origin, in the unit square $U = [0,1]^2$. The problem is to construct $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coincides with a point in $P_{n}$ and the total area covered by the rectangles is maximized. We would term the above rectangles as emph{anchored rectangles}. The longstanding conjecture has been that at least half of $U$ can be covered when anchored rectangles are properly placed. Dumitrescu and T{o}th cite{Dumitrescu2012} have shown a construction method that can cover at least $0.09121$, i.e., roughly $9%$ of the area.

An Existential Proof of the Conjecture on Packing Anchored Rectangles

Let $P_{n}$ be a set of $n$ points, including the origin, in the unit square $U = [0,1]^2$. We consider the problem of constructing $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coincides with a point in $P_{n}$ and the total area covered by the rectangles is maximized cite{ibmpuzzle}, cite{Winkler2007}, cite{Winkler2010a}, cite{Winkler2010b}. The longstanding conjecture has been that at least half of $U$ can be covered when such rectangles are properly placed. In this paper, we give an existential proof of the conjecture.