# How to divide a rectangle into fewest equally sized nearly-square sub-rectangles

I want to divide a rectangle into grid rows and columns.

I need the grid to have fewer rather than more rows and columns.

Here's an illustration

Requirements for each cell (eg the blue cell above):

• The height of each cell in the grid should be equally sized.

• The width of each cell in the grid should be equally sized.

• The ratio of each cell width & height should be 1.25 or less.

Max(width,height) / Min(width,height) <= 1.25


Is there an algorithm to calculate the number of rows and columns needed to produce the fewest number of "square-ish" sub-rectangles?

You need $n,m$ with $\frac 45\le \frac{w/n}{h/m}\le\frac 54$ and $nm$ minimal (here $w,h$ are the dimensions of the given large rectangle adn $n,m$ the number of columns and rows we should produce). The bounds can also be rewritten as $$\alpha\le \frac nm\le \beta$$ with $\alpha=\frac{4w}{54}$ and $\beta=\frac{5w}{4h}$. This is generally solved by the "simplest" fraction in the range $[\alpha,\beta]$, for which several methods exist. An easily rememberable one is this:
1. Start with $n'=0,m'=1$, $n''=1,m''=0$
2. Let $n=n'+n''$, $m=m'+m''$
3. If $\frac nm<\alpha$, let $n'=n,m'=m$ and go back to step 2
4. If $\frac nm>\beta$, let $n''=n,m''=m$ and go back to step 2
5. At this point $\alpha\le \frac{n}{m}\le\beta$; we are done and have found $n$ and $m$ as desired.
Why is the found $n,m$ optimal? One can show that any fraction $\frac xy$ between $\frac {n'}{m'}$ has $x\ge n'+n$, $y\ge m'+m$, hence $xy\ge (n'+n)(m'+m)>nm$. Similar for $\frac xy$ between $\frac nm$ and $\frac {n''}{m''}$.