Dominic van der Zypen posed an interesting Box stacking problem. This is a spin-off question.

Let a collection of rectangles $r_1,\ldots,r_n$ be given by their side lengths in $\mathbb{R}$. Let $R$ be a rectangle of minimum area enclosing the rectangles arranged in the plane without overlap (i.e., with disjoint interiors).

Q. Is there an example where not all the rectangles have sides aligned with the sides of $R$?

In other words, where at least one rectangle's sides are not parallel to the sides of $R$? Is it ever advantageous to "tilt" one or more rectangles to achieve a minimal area?

  • 17
    $\begingroup$ I think this should work. Consider 2 rectangles with r1 having dimensions 1x11 and r2 having area 10x100. Then the packings that have aligned sides have enclosing areas at least 1100, but if you "lean" r1 against the end of r2 then you can get an enclosing rectangle with area around 1025. $\endgroup$ Apr 27 '19 at 19:06
  • $\begingroup$ There was mention of some research showing how one could pack (1+ delta)n^2 unit squares in a square of side (1 + epsilon)n. Consider searching "Packing squares in a square. There is also "shipping a pool cue" in the diagonal of a packing box. Gerhard "Can't Name Any Names Yet" Paseman, 2019.04.27. $\endgroup$ Apr 27 '19 at 19:09

          @YosemiteStan's example.
          enter image description here
          Detail: Tilt angle $=\sin ^{-1}\left(5 \sqrt{\frac{2}{61}}\right) \approx 65^\circ$.

  • 2
    $\begingroup$ Actually, in the first packing the smaller rectangle should lie on the top of the larger one, giving the intended area of 11*100=1100. $\endgroup$ Apr 27 '19 at 19:51
  • $\begingroup$ @VictorProtsak: Thanks; corrected. $\endgroup$ Apr 27 '19 at 19:55
  • $\begingroup$ The first packing is $100\cdot (10+1) = 1100$, but I think the second packing is $\left( \frac{10}{61}(11+6\sqrt{22})+100 \right)\cdot 10\approx 1064.2$, so the example is valid, but $1025$ from the original comment is not so precise. To me, it is hard to estimate visually by staring at the figure, which packing is better, but I can see that the "leaning" thin box is more upright than $45^\circ$. $\endgroup$ Apr 29 '19 at 10:07
  • $\begingroup$ @JeppeStigNielsen: "more upright": Yes, about $65^\circ$. See added detail. $\endgroup$ Apr 29 '19 at 11:52
  • 1
    $\begingroup$ @JeppeStigNielsen: You can increase the length from $100$ to an arbitrarily large length, in which case it is clear that the bottom picture covers less area. $\endgroup$
    – Tony Huynh
    Apr 29 '19 at 12:43

The classic answer to this is a paper of Erdos and Graham 'On packing squares with equal squares'. Given a square of side $n+\varepsilon$, where $0<\varepsilon<1$, we can obviously fit in $n^2$ unit squares, and it's fairly trivial to check that if the squares are axis aligned this is best possible (count the squares intersecting vertical lines on the integers). Obviously, this means about $2\varepsilon n$ area is going to waste.

But Erdos and Graham show one can cover asymptotically all but $n^{7/11}$ area, using skew angles - this is maybe more surprising than Yosemite Stan's example (which also works perfectly well).

  • 4
    $\begingroup$ However the question allows any rectangle and one can get pack a bunch of unit cubes in a rectangle with no wasted space. $\endgroup$ Apr 28 '19 at 7:42
  • 2
    $\begingroup$ Square packing was my first thought as well, some nice pictures are available at www2.stetson.edu/~efriedma/squinsqu. However on second thought it's apparent that square packing is not relevant to this question. The minimal area rectangle for any collection of equal sized squares is trivially realized simply by stacking them all in a single line. $\endgroup$
    – Brady Gilg
    Apr 30 '19 at 6:06
  • $\begingroup$ @BradyGilg Link to that page in Erich Friedman's packing center is now erich-friedman.github.io/packing/squinsqu $\endgroup$ Dec 7 '20 at 0:53

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.