17

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?

randomizer
  • 741
  • 5
  • 15
  • 3
    @AndrásSalamon A $5 \times 6$ rectangle is a counterexample for the optimality of Euclid's algorithm. – randomizer Aug 02 '13 at 11:03
  • 4
    Already asked here: http://mathoverflow.net/questions/44524/minimum-tiling-of-a-rectangle-by-squares, some interesting pointers are given. – minar Aug 02 '13 at 14:31
  • @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 Aug 02 '13 at 14:44
  • 4
    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 Aug 02 '13 at 15:18
  • 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 Aug 02 '13 at 15:30
  • 1
    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 Aug 02 '13 at 22:47
  • 2
    @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 Aug 07 '13 at 04:43
  • @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 Aug 07 '13 at 08:47
  • This is same as finding greatest common divisor. See Euclid –  Nov 24 '13 at 13:05
  • @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 Nov 24 '13 at 13:11

0 Answers0