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?
$\begingroup$
$\endgroup$
10
-
3$\begingroup$ @AndrásSalamon A $5 \times 6$ rectangle is a counterexample for the optimality of Euclid's algorithm. $\endgroup$– randomizerAug 2, 2013 at 11:03
-
4$\begingroup$ Already asked here: mathoverflow.net/questions/44524/…, some interesting pointers are given. $\endgroup$– minarAug 2, 2013 at 14:31
-
4$\begingroup$ Minimum number of integer-sided squares needed to tile an m by n rectangle from The On-Line Encyclopedia of Integer Sequences. oeis.org/A219158 $\endgroup$– Mohammad Al-TurkistanyAug 2, 2013 at 15:18
-
1$\begingroup$ 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?) $\endgroup$– Marzio De BiasiAug 2, 2013 at 22:47
-
2$\begingroup$ @MarzioDeBiasi There is a counterexample for this equation: $h(2 \cdot 53 + 6,53) = h(53 + 6,53) = 11$ (see int-e.eu/~bf3/squares). $\endgroup$– randomizerAug 7, 2013 at 4:43
|
Show 5 more comments