An algorithm for deciding if a polyomino tiles the plane
Gambini, Ian ; Vuillon, Laurent
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 147-155 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007012
Classification:  68R15,  52C20 
@article{ITA_2007__41_2_147_0,
     author = {Gambini, Ian and Vuillon, Laurent},
     title = {An algorithm for deciding if a polyomino tiles the plane},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {41},
     year = {2007},
     pages = {147-155},
     doi = {10.1051/ita:2007012},
     mrnumber = {2350641},
     zbl = {pre05235505},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_2_147_0}
}

Gambini, Ian; Vuillon, Laurent. An algorithm for deciding if a polyomino tiles the plane. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 147-155. doi : 10.1051/ita:2007012. http://gdmltest.u-ga.fr/item/ITA_2007__41_2_147_0/

[1] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: a methodology for the Enumeration of Combinatorial Objects. J. Difference Equ. Appl. 5 (1999) 435-490. | Zbl 0944.05005

[2] D. Beauquier and M. Nivat, On translating one polyomino to tile the plane. Discrete Comput. Geom. 6 (1991) 575-592. | Zbl 0754.05030

[3] M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons. Discrete Math. 154 (1996) 1-25. | Zbl 0858.05006

[4] M. Bousquet-Mélou. Habilitation. LABRI Université de Bordeaux 1 (1996). | MR 1395445

[5] S.J. Chang and K.Y. Lin. Rigorous results for the number of convex polygons on the square and honeycomb lattices. J. Phys. A 21 (1988) 2635-2642.

[6] T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to algorithms. Chapt. 34, MIT Press (1990) 853-885. | Zbl 1047.68161

[7] A. Daurat and M. Nivat. Salient and Reentrant Points of Discrete Sets, in Proc. of the nineth International Workshop on Combinatorial Image Analysis (IWCIA 2003), volume 12 of Electronic Notes in Discrete Mathematics. Elsevier (2003). | MR 2155847 | Zbl 1115.52300

[8] A. Del Lungo, E. Duchi, A. Frosini and S. Rinaldi, Enumeration of convex polyominoes using the ECO method, in Discrete Models for Complex Systems, DMCS'03, edited by M. Morvan and É. Rémila, Discrete Mathematics and Theoretical Computer Science Proceedings AB, 103-116. | Zbl 1032.05003

[9] M. Delest and X. Viennot, Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34 (1984) 169-206. | Zbl 0985.68516

[10] I. Gambini, A Method for Cutting Squares Into Distinct Squares. Discrete Appl. Math. 98 (1999) 65-80. | Zbl 0935.05024

[11] S.W. Golomb. Polyominoes, Princeton science library (1994). | Zbl 0831.05020

[12] P. Hubert and L. Vuillon. Complexity of cutting words on regular tilings. Eur. J. Combin. 28 (2007) 429-438. | Zbl 1111.68095

[13] D.E. Knuth, J.H. Morris and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput. 6 (1997) 323-350. | Zbl 0372.68005

[14] P. Leroux, E. Rassart and A. Robitaille, Enumeration of symmetry classes of convex polyminoes in the square lattice. Adv. Appl. Math. 21 (1998) 343-380. | Zbl 0921.05024

[15] P. Leroux and E. Rassart, Enumeration of symmetry classes of parallelogram polyminoes. Ann. Sci. Math. Québec 25 (2001) 53-72. | Zbl 1002.05015