A PTAS for the Square Tiling Problem

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 − ϵ 2 log ⁡ n ) for any given ϵ ≤ 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.

Authors

• Amihood Amir
• Alberto Apostolico
• Gad M. Landau
• Ely Porat
• Oren Sar Shalom

Keywords

• Two dimensional tiling
• Finite alphabets
• NP-Hardness