The Prague Stringology Conference 2006
Srečko Brlek and Xavier Provençal
On the Problem of Deciding If a Polyomino Tiles the Plane by Translation
| Abstract: |
| The words that tile the plane by translation are characterized by the Beauquier-Nivat condition. By using the constant time algorithms for computing the longest common extensions in two words, we provide a linear time algorithm in the case of pseudo-square polyominoes, improving the previous quadratic algorithm of Gambini and Vuillon. For pseudo-hexagon polyominoes not containing arbitrarily large square factors we also have a linear algorithm. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |