This seems like something that should have a known answer, but I haven't found it after some time alternating between searching and generating multiple pages of algebra. I'm interested in $k=4$ and $k=6$, but I'll phrase it for general $k$:

Given $k$ identical rectangles of dimension $a \times b$ (let's assume $a \leq b$), what is the smallest square that can contain them if the rectangles do not overlap and can be placed at any orientation (i.e., not necessarily parallel to the square's sides)?

  • 1
    $\begingroup$ It is not clear from your wording what constraints are given and what freedoms are allowed. For example, for k=1 and a much smaller than b, I can use a square with side length close to 0.7 times b, if I get to choose the packing. Do I get to choose? Or are the orientations fixed and I have to find the smallest square covering them? Gerhard "What Are The Rules Here?" Paseman, 2018.08.31. $\endgroup$ – Gerhard Paseman Aug 31 '18 at 22:50
  • $\begingroup$ What motivates this question? And why are the cases $k=4$ and $k=6$ of special interest? $\endgroup$ – Wlodek Kuperberg Nov 6 '18 at 21:50

You might recheck your values for k=1 and 2. In particular, an ab rectangle fits in a square of side length (a+b)/c, where c*c=2. For a less than (c-1)b, this improves upon a square of side length b. For k=2 and a smaller than (c-1)b/2, a similar diagonal packing works.

One approach you can use is to consider packing rectangles into the smallest rectangle, and then fitting this larger rectangle inside a square. This may not achieve optimum, but it leverages earlier work and should give near optima.

Gerhard "And Check Out Pack-O-Mania Website" Paseman, 2018.08.31.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.