<p>Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares.</p>

<p>Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best known algorithm?</p>

CC BY-SA 3.0
2013-08-02T11:03:23.053Z
@AndrásSalamon A $5 \times 6$ rectangle is a counterexample for the optimality of Euclid's algorithm.
randomizer
CC BY-SA 3.0
2013-08-02T14:31:22.140Z
Already asked here: http://mathoverflow.net/questions/44524/minimum-tiling-of-a-rectangle-by-squares, some interesting pointers are given.
minar
CC BY-SA 3.0
2013-08-02T14:44:43.440Z
@MohammadAl-Turkistany Given that the size of input is $\log n + \log m$, it is not surprising, but I am mainly interested in an efficient algorithm in $n$ and $m$.
randomizer
CC BY-SA 3.0
2013-08-02T15:18:22.223Z
Minimum number of integer-sided squares needed to tile an m by n rectangle from The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A219158
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-08-02T15:30:20.797Z
I guess the problem is strongly NP-complete, so I guess no hope for Polynomial Time algorithm in $m$ and $n$ unless P=NP.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-08-02T22:47:59.573Z
Let $h(n,m)$ be the minimum number of integer-sided squares that tile an $(n,m)$ rectangle, if $k\geq2, 0\leq d <n$, do you know if this equation always holds: $h(n,kn+d) = (k-1) + h(n,n+d)$? (i.e.  can we greedily remove k-1 $n\times n$ squares and reduce the problem to tiling an "almost square" with squares?)
Marzio De Biasi
CC BY-SA 3.0
2013-08-07T04:43:05.890Z
@MarzioDeBiasi There is a counterexample for this equation: $h(2 \cdot 53 + 6,53) = h(53 + 6,53) = 11$ (see http://int-e.eu/~bf3/squares/).
randomizer
CC BY-SA 3.0
2013-08-07T08:47:08.780Z
@nlc: great !... then another problem could be: if the equation holds for k, does it hold for all k' > k? (if the answer is yes then another problem is: given n what is the least k for which the equation holds :-)
Marzio De Biasi
CC BY-SA 3.0
2013-11-24T13:11:46.570Z
@Patrick, I think you're assuming that the squares all have to be the same size. This is not an assumption the OP wants. Or maybe you're assuming that the greedy algorithm always gives the best tiling. It doesn't. See Mario De Biasi and nlc's comments above.
Peter Shor 
<ds.algorithms><co.combinatorics>
Tiling a rectangle with the fewest squares
randomizer
# Tiling a rectangle with the fewest squares

(Asked by: username_0 on 2013-08-02)

Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares.

Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best known algorithm?

**Tags:** ds.algorithms, co.combinatorics

> **Comments:**
> **username_0**: @AndrásSalamon A $5 \times 6$ rectangle is a counterexample for the optimality of Euclid's algorithm.  
> **username_1**: Already asked here: http://mathoverflow.net/questions/44524/minimum-tiling-of-a-rectangle-by-squares, some interesting pointers are given.  
> **username_0**: @MohammadAl-Turkistany Given that the size of input is $\log n + \log m$, it is not surprising, but I am mainly interested in an efficient algorithm in $n$ and $m$.  
> **username_2**: Minimum number of integer-sided squares needed to tile an m by n rectangle from The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A219158  
> **username_2**: I guess the problem is strongly NP-complete, so I guess no hope for Polynomial Time algorithm in $m$ and $n$ unless P=NP.  
> **username_3**: Let $h(n,m)$ be the minimum number of integer-sided squares that tile an $(n,m)$ rectangle, if $k\geq2, 0\leq d <n$, do you know if this equation always holds: $h(n,kn+d) = (k-1) + h(n,n+d)$? (i.e.  can we greedily remove k-1 $n\times n$ squares and reduce the problem to tiling an "almost square" with squares?)  
> **username_0**: @MarzioDeBiasi There is a counterexample for this equation: $h(2 \cdot 53 + 6,53) = h(53 + 6,53) = 11$ (see http://int-e.eu/~bf3/squares/).  
> **username_3**: @nlc: great !... then another problem could be: if the equation holds for k, does it hold for all k' > k? (if the answer is yes then another problem is: given n what is the least k for which the equation holds :-)  
> **username_4**: @Patrick, I think you're assuming that the squares all have to be the same size. This is not an assumption the OP wants. Or maybe you're assuming that the greedy algorithm always gives the best tiling. It doesn't. See Mario De Biasi and nlc's comments above.  

---

## 0 answers

