A PTAS for the Square Tiling Problem

作者：Amir Amihood^*; Apostolic Alberto; Landau Gad M; Porat Ely; Shalom Oren Sar

来源：Theoretical Computer Science, 2015, 562: 33-45.

DOI：10.1016/j.tcs.2014.09.012

• Two dimensional tiling
• Finite alphabets
• NP-Hardness

The Square Tiling Problem was recently introduced as equivalent to the problem of reconstructing an image from patches and a possible general-purpose indexing tool. Unfortunately, the Square Tiling Problem was shown to be NP-hard. A 1/2-approximation is known.
We show that if the tile alphabet is fixed and finite, there is a Polynomial Time Approximation Scheme (PTAS) for the Square Tiling Problem with approximation ratio of (1 - epsilon/2 log n) for any given epsilon <= 1.
Another topic handled in this paper is the NP-hardness of the Tiling problem with an infinite alphabet. We show that when the alphabet is not bounded, even the decision version for rectangles of size 3n is NP-Complete.

• 出版日期2015-1-11