17
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ @AndrásSalamon A $5 \times 6$ rectangle is a counterexample for the optimality of Euclid's algorithm. $\endgroup$ – nlc Aug 2 '13 at 11:03
  • 4
    $\begingroup$ Already asked here: mathoverflow.net/questions/44524/…, some interesting pointers are given. $\endgroup$ – minar Aug 2 '13 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-Turkistany Aug 2 '13 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 Biasi Aug 2 '13 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$ – nlc Aug 7 '13 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.