T. Buchwald and G. Scheithauer,
A 5/9 Theorem on Packing Squares into a Square
Within the field of two-dimensional cutting and packing problems
only few statements are known whether a given set of small
rectangular items can entirely be packed into a rectangular bin.
Even if each single item fits within the bin
and their total area is only a small percentage of the bin area,
if two or more items have to be packed, then
there is no guarantee that all items can be placed.
However, if each item has a length (width) at most half of the bin
length (width), then any set of items with total area at most
50 percent of the bin area can be packed.
In this paper, we consider the particular case of only quadratic items
and a square bin.
Then, obviously, any set of items with total area at most 25 percent
can be packed.
We prove, any set of quadratic items can be packed into a square
if it satisfies the two conditions:
(1) the length of each item is not longer than half of the bin length
the total area of items is at most 5/9 of the bin area.
Moreover, we show that the value 5/9 is best-possible.
Additionally, we prove, if (1) is fulfilled and the total area of items is
sufficiently large, then a packing with area utilization at least
4/9 of the bin area can be achieved.
Finally, we state that all patterns considered during the proofs
possess the guillotine property.
(Preprint MATH-NM-04-2016, TU Dresden, December 2016)