An Algorithm for Deciding If a Polyomino Tiles the Plane by Translations
Ian Gambini, Laurent Vuillon · 2007
For polyominoes coded by their boundary word, we describe a quadratic O(n²) algorithm in the boundary length n which improves the naive O(n^4) algorithm. Techniques used emanate from algorithmics, discrete geometry and combinatorics on words.