AN ALGORITHM FOR DECIDING IF A POLYOMINO TILES THE PLANE

摘要

For polyominoes coded by their boundary word, we describe a quadratic O(n~2) 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.