3
$\begingroup$

In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply connected region with these rectangle shapes is NP-complete. However the number of rectangle shapes $10^6$ seems pretty extreme. Maybe it's hard to close the gap on P vs. NP-complete for tiling in terms of the number of rectangle shapes available, but what if we allow more complex pieces such as non-rectangular Tetris pieces and larger non-rectangular pieces? (We could insist the piece shapes are all simply connected, but I'm not adamant about that).

Can we show NP-completeness for tiling a simply connected region with a much smaller set of (potentially non-rectangular) pieces available, compared to $10^6$?

The authors mention and rely upon an NP-completeness result for tiling with "Generalized Wang Tiles" that seem to use coloring as well as shape, and claim that NP-completeness can be achieved with a fixed set of 23 generalized Wang tiles. However I wasn't able to decipher this result to figure out how many ordinary non-colored (and e.g., perhaps also simply connected) tile shapes are needed to establish NP-completeness.

Improve this question
$\endgroup$
3
  • $\begingroup$ Is showing that a certain class of simply-connected regions is NP-complete (e.g. all $(2, m)$ rectangles) enough, or must the selected set of pieces be NP-complete for all simply-connected regions? $\endgroup$
    – orlp
    Sep 19, 2015 at 17:08
  • $\begingroup$ @orlp According to how I was taught, if the problem is NP-complete for a subclass of problem instances then it is NP-complete overall (as long as there is no dramatic input size reduction of the problem for the subclass), although some other subclasses may be easy. So if hardness can be shown for tiling of $2 \times m$ rectangle regions for a certain fixed set of tiling pieces, in my book that would definitely qualify. But the input size would have to be more like $O(m)$, not $O(\log m)$, since the encoding of an arbitrary simply connected region is proportional to the number of unit squares. $\endgroup$
    – user2566092
    Sep 19, 2015 at 17:21
  • $\begingroup$ @orlp However I should say, although it wasn't my original intent, if NP-completeness can be shown for $2 \times m$ regions with a fixed set of tile shapes when the input size of the region to be tiled is considered to be $O( \log m)$, that would still be interesting -- just not what I originally intended. $\endgroup$
    – user2566092
    Sep 19, 2015 at 17:28

1 Answer 1

Reset to default
3
$\begingroup$

Found their paper on ArXiv. It is quite easy to go from coloured Wang tiles to uncoloured shapes by introducing zig-zag boundaries, like a jig-saw, as illustrated in their Figure 3. So then still 23 tiles are needed, as colours are simply replaced by boundaries.

Their contribution is to move from boundaries to only rectangular tiles. The authors state in Lemma 3.3 how many rectangles are needed to replace coloured Wang tiles, and a long Section 5 is devoted to the proof of that lemma.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I wasn't clear whether the notion of "colored" Wang tiles directly extended (with the same number of tiles) to uncolored shapes. So I guess the answer is we can get down to 23 shapes or fewer. $\endgroup$
    – user2566092
    Sep 20, 2015 at 22:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.