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?


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

  • $\begingroup$ yes holes could be allowed, but then it goes really complicated.. okay you got me a good idea: i take as many rectangles as i can have in a square alike and the rest dont go in there. this is close enough for me. thanks! $\endgroup$ – reox Aug 23 '11 at 16:25

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.