Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
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! –  reox Aug 23 '11 at 16:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.