Minimize the side length of rectangles in a cluster

Question

I need to cluster some rectangles which have all the same size, for example $a = 10$ and $b = 20$.

My goal is to create a new rectangle x where the side length a' and b' is minimal, so it should be more or less a cube.

my first approach simply this: n is the number of rectangles.

$$a' = \sqrt(n)$$ $$b' = \frac n {a'}$$

Both values are rounded down to the next integer.

My problem is that is works great for the most values, for example $n = 24$, I get $a' = 4$ and $b' = 6$. Only when i use 10, i have a problem because $\sqrt(10) = 3$, so i have $b' = 3$ as well... but it should be $a'=2$ and $b'=5$...

is there a better way to calculate this?

Answer 1

If I understand correctly, you have $n$ rectangles, all of size $a \times b$. You want to arrange them in a rectangular tiling to minimize the maximum dimension. In your example, you have $24$ rectangles, each $10 \times 20$. If you arrange them in a $4 \times 6$ array, you get $80 \times 60$, which is pretty close to square.

Is it allowable to have holes? If we change the example to $23$ rectangles, is the right answer $1 \times 23$ giving outside dimensions of $20 \times 230$ or as above, leaving out one rectangle?

Assuming holes are not allowed, you need to factor $n$ with the ratio of the factors as close to $\frac{b}{a}$ as possible. So you would like the factors to be close to $\sqrt{\frac{na}{b}}$ and $\sqrt{\frac{nb}{a}}$. If holes are allowed, you could look for numbers slightly greater than $n$ that have factors closer to desired (as in the case of $23$ vs $24$ above).