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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.