An algorithm for deciding if a polyomino tiles the plane
- 1 April 2007
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 41 (2) , 147-155
Abstract
For polyominoes coded by their boundary word, we describe a quadratic O(n2) algorithm in the boundary length n which improves the naive O(n4) algorithm. Techniques used emanate from algorithmics, discrete geometry and combinatorics on words.Keywords
This publication has 12 references indexed in Scilit:
- Complexity of cutting words on regular tilingsEuropean Journal of Combinatorics, 2005
- Salient and Reentrant Points of Discrete SetsElectronic Notes in Discrete Mathematics, 2003
- A method for cutting squares into distinct squaresDiscrete Applied Mathematics, 1999
- ECO:a methodology for the enumeration of combinatorial objectsJournal of Difference Equations and Applications, 1999
- Lecture Hall PartitionsThe Ramanujan Journal, 1997
- A method for the enumeration of various classes of column-convex polygonsDiscrete Mathematics, 1996
- Polyominoes1994
- On translating one polyomino to tile the planeDiscrete & Computational Geometry, 1991
- Rigorous results for the number of convex polygons on the square and honeycomb latticesJournal of Physics A: General Physics, 1988
- Algebraic languages and polyominoes enumerationTheoretical Computer Science, 1984