Maximum number of $m\times n$ rectangles that fit in a $k \times k$ square

Question

I'm sure this has been asked before but I have searched for ages and can't quite find what I'm looking for. Here's the problem:

Essentially what is the maximum possible number of rectangles of a given size $(m \times n)$ that will fit without overlapping in a given sized square ($k \times k$).

How can you tackle it?

Consider $\lfloor{\frac km}\rfloor$ and $\lfloor{\frac kn} \rfloor$. — Vishu, Apr 21 '20 at 18:27
Well there's clearly a lower bound as Robert said below, but it's unclear whether there can be more rectangles that fit in the opposite orientation. — e2.71828, Apr 22 '20 at 11:59

Robert Israel · Answer 1 · 2020-04-21T19:15:19.807

1

In general, this kind of packing problem is very difficult. Of course there is an obvious upper bound of $\lfloor k^2/(mn) \rfloor$ from consideration of areas, and a lower bound of $\lfloor k/m \rfloor \lfloor k/n \rfloor$. There can be a lot of room between these.

See e.g. Recursive partitioning approach for the Manufacturer's Pallet Loading Problem.

edited Apr 21 '20 at 19:15

answered Apr 21 '20 at 18:53

Robert Israel

448,999

Maximum number of $m\times n$ rectangles that fit in a $k \times k$ square

1 Answers1