0
$\begingroup$

In the image there are 2 rectangles: first with a ratio of 1:2.5 and the second with a ratio 0.65:1.

Example images

Trying to pack biggest squares possible, in the first example 4 can be packed and in the second 9.

I'm no mathematician so although there's clearly something going on, I can't really put it into a formula.

How do I mathematically determine the minimum number of any-size squares to completely fill a rectangle of a given ratio?

$\endgroup$
  • $\begingroup$ This looks a lot like the knapsack problem/ bin packing problem with relaxed integrality constraints. $\endgroup$ – Ragnar Apr 21 '15 at 22:00
1
$\begingroup$

I think a better way to view this is to multiply the sides of the original rectangle up until they are both natural numbers and think of a grid of unit squares that you need to cover with squares with natural side. Your $2.5 \times 1$ rectangle becomes $5 \times 2$ and your $0.65 \times 1$ becomes $13 \times 20$. Your two examples use the greedy algorithm-find the largest square that fits in the remaining region, cut it out, and continue. The good news is that the proces will terminate. The bad news is that it may not be optimal. An example is a $5 \times 6$ rectangle, which the greedy algorithm cuts into a $5 \times 5$ square and five $1 \times 1$'s for a total of six. You can cut it into two $3 \times 3$ squares and three $2 \times 2$'s for five.

$\endgroup$

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.