A 5/9 Theorem on Packing Squares into a Square

Abstract

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 and (2) 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.

PDF, (Preprint MATH-NM-04-2016, TU Dresden, December 2016)

Back