2
$\begingroup$

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)?

$\endgroup$
  • 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
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Just a note to indicate why this question might not be straightforward, now that it's been bumped to the homepage. For $k=2$ rectangles of size $a \times b = 1 \times 6$, the diagonal packing is better than $6$, because $2a < (\sqrt{2}-1) b$, as Gerhard mentions in his answer. But this is not the optimal packing, as the figure below indicates: Tilting the rectangles differently fits in a smaller square.


          Rect2Square
          The diagonal packing for two $1 \times 6$ rectangles is suboptimal. The blue squares are identical.
It would be interesting to find an example where the rectangles are necessarily not parallel in an optimal packing.

$\endgroup$
  • 1
    $\begingroup$ For your last question (sorry, I do have to use words instead of pictures), I suspect that four copies of a $1\times(1-\epsilon)$-rectangle (for small $\epsilon >0$) can best be packed into a square when not parallel. I have the feeling (but have not attempted to prove) that when parallel, the smallest square has side length 2. But if we are allowed to use the rectangles in two different orientations (related by a 90 degree rotation), then we can pack them into a square of side length $2-\epsilon$. I imagine a ring-like arrangement in which the rectangles leave a small hole in the middle. $\endgroup$ – M. Winter Sep 2 at 21:20

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.