For polyominoes coded by their boundary word, we describe a quadratic algorithm in the boundary length which improves the naive algorithm. Techniques used emanate from algorithmics, discrete geometry and combinatorics on words.
Mots-clés : polyominoes, tiling the plane by translation, theorem of Beauquier-Nivat, pseudo-square, pseudo-hexagon, enumeration of special classes of polyominoes
@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},
pages = {147--155},
publisher = {EDP-Sciences},
volume = {41},
number = {2},
year = {2007},
doi = {10.1051/ita:2007012},
mrnumber = {2350641},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007012/}
}
TY - JOUR AU - Gambini, Ian AU - Vuillon, Laurent TI - An algorithm for deciding if a polyomino tiles the plane JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2007 SP - 147 EP - 155 VL - 41 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2007012/ DO - 10.1051/ita:2007012 LA - en ID - ITA_2007__41_2_147_0 ER -
%0 Journal Article %A Gambini, Ian %A Vuillon, Laurent %T An algorithm for deciding if a polyomino tiles the plane %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2007 %P 147-155 %V 41 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2007012/ %R 10.1051/ita:2007012 %G en %F 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) no. 2, pp. 147-155. doi : 10.1051/ita:2007012. http://www.numdam.org/articles/10.1051/ita:2007012/
[1] ,, and, ECO: a methodology for the Enumeration of Combinatorial Objects. J. Difference Equ. Appl. 5 (1999) 435-490. | Zbl
[2] and, On translating one polyomino to tile the plane. Discrete Comput. Geom. 6 (1991) 575-592. | Zbl
[3] , A method for the enumeration of various classes of column-convex polygons. Discrete Math. 154 (1996) 1-25. | Zbl
[4] . Habilitation. LABRI Université de Bordeaux 1 (1996). | MR
[5] and. Rigorous results for the number of convex polygons on the square and honeycomb lattices. J. Phys. A 21 (1988) 2635-2642.
[6] , and, Introduction to algorithms. Chapt. 34, MIT Press (1990) 853-885. | Zbl
[7] and. 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 | Zbl
[8] ,, and, 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
[9] and, Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34 (1984) 169-206. | Zbl
[10] , A Method for Cutting Squares Into Distinct Squares. Discrete Appl. Math. 98 (1999) 65-80. | Zbl
[11] . Polyominoes, Princeton science library (1994). | Zbl
[12] and. Complexity of cutting words on regular tilings. Eur. J. Combin. 28 (2007) 429-438. | Zbl
[13] , and. Fast pattern matching in strings. SIAM J. Comput. 6 (1997) 323-350. | Zbl
[14] , and, Enumeration of symmetry classes of convex polyminoes in the square lattice. Adv. Appl. Math. 21 (1998) 343-380. | Zbl
[15] and, Enumeration of symmetry classes of parallelogram polyminoes. Ann. Sci. Math. Québec 25 (2001) 53-72. | Zbl
Cité par Sources :
