Optimal set of rectangle sizes to pack arbitrary rectangle

geometrypacking-problem

I'm looking to build a set of wooden storage boxes of various standard sizes for storing small objects.

I would like to choose a set of "optimal" box sizes (outside dimensions) for filling arbitrary rectangular spaces.

I define "optimal" here as:

  • minimize wasted space after packing;

  • minimize different box sizes; and

  • minimize the number of boxes required to fill the space, assuming the definition of some largest box dimension.

In 1 dimension this is straightforward: a set of "boxes" of sizes { 16, 8, 4, 2, 1 } can fill any 1-dimensional space with less than 1 unit of waste with my definition of "optimal" as above.

For 2-dimensional spaces, I don't know how to solve this. It seems like there should be some geometric answer to this, but I'm not versed enough in packing problems to know where to start looking.

I was wondering if anybody on here could help solve this, or point the way to an answer?

Thanks!

Best Answer

I'm not sure if this is optimal, but it works.

My collection optimises "no wasted space", and it also minimises the number of boxes required in the sense that "the most efficient tiling of any space" is obtained by using the biggest boxes first. However, you may feel that there are too many boxes.

For $2$-dimensional space, I use $(x,y)$ to denote rectangles with side lengths $x$ and $y$.

  1. $\{(1,1), (1,2), (1,2), (2,2)\}$ will fill all spaces (with integer sides) up to $3\times 3$ with no gaps (with the greedy algorithm)
  2. $\{(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)\}$ will fill all spaces with integer sides up to $7\times 7$ with no gaps (with the greedy algorithm)

More generally, the collections of boxes are defined by:

one of each box of size $(x,x)$, two of each box of size $(x,y)$ with $x\neq y$, where $x,y \in \{1,2,4,8,...\}$.

I conjecture that the collection of boxes generated in this way will always tile larger 2d spaces with no gaps using the greedy algorithm. (I have verified this for the two cases above, but not for e.g. $15\times 15$, $31\times 31$,...)

By "using the greedy algorithm", I mean that if you attempt to tile some space, you just have to start with the biggest box, then use the second biggest box, etc.

I suspect that there maybe a more optimal solution which makes use of golden-ratio-eqsue maths.

Related Question