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.

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.

DOI : 10.1051/ita:2007012
Classification : 68R15, 52C20
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 = {https://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  - https://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 https://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. https://www.numdam.org/articles/10.1051/ita:2007012/

[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

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

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

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

[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

[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 | Zbl

[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

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

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

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

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

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

[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

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

  • Ascolese, Michela; Frosini, Andrea Proving a conjecture on prime double square tiles, Discrete Applied Mathematics, Volume 350 (2024), p. 71 | DOI:10.1016/j.dam.2024.02.022
  • Amano, Kazuyuki; Haruyama, Yoshinobu On the Number of p4-Tilings by an n-Omino, International Journal of Computational Geometry Applications, Volume 29 (2019) no. 01, p. 3 | DOI:10.1142/s0218195919400016
  • Brand, Michael Small polyomino packing, Information Processing Letters, Volume 126 (2017), p. 30 | DOI:10.1016/j.ipl.2017.06.004
  • Winslow, Andrew An Optimal Algorithm for Tiling the Plane with a Translated Polyomino, Algorithms and Computation, Volume 9472 (2015), p. 3 | DOI:10.1007/978-3-662-48971-0_1
  • Yang, Jed Rectangular tileability and complementary tileability are undecidable, European Journal of Combinatorics, Volume 41 (2014), p. 20 | DOI:10.1016/j.ejc.2014.03.008
  • Blondin Massé, Alexandre; Tall, Amadou Makhtar; Tremblay, Hugo On the Arithmetics of Discrete Figures, Language and Automata Theory and Applications, Volume 8370 (2014), p. 198 | DOI:10.1007/978-3-319-04921-2_16
  • Gambini, I.; Vuillon, L. Non-lattice-periodic tilings of R3 by single polycubes, Theoretical Computer Science, Volume 432 (2012), p. 52 | DOI:10.1016/j.tcs.2012.01.014
  • KLAPPENECKER, ANDREAS; LEE, HYUNYOUNG; WELCH, JENNIFER L. SCHEDULING SENSORS BY TILING LATTICES, Parallel Processing Letters, Volume 20 (2010) no. 01, p. 3 | DOI:10.1142/s0129626410000028
  • Brlek, S.; Provençal, X.; Fédou, Jean-Marc On the tiling by translation problem, Discrete Applied Mathematics, Volume 157 (2009) no. 3, p. 464 | DOI:10.1016/j.dam.2008.05.026
  • Ollinger, Nicolas Tiling the Plane with a Fixed Number of Polyominoes, Language and Automata Theory and Applications, Volume 5457 (2009), p. 638 | DOI:10.1007/978-3-642-00982-2_54

Cité par 10 documents. Sources : Crossref