An algorithm for deciding if a polyomino tiles the plane

Ian Gambini; Laurent Vuillon

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 2, page 147-155
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Gambini, Ian, and Vuillon, Laurent. "An algorithm for deciding if a polyomino tiles the plane." RAIRO - Theoretical Informatics and Applications 41.2 (2007): 147-155. <http://eudml.org/doc/250073>.

@article{Gambini2007,
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. },
author = {Gambini, Ian, Vuillon, Laurent},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Polyominoes; tiling the plane by translation; theorem of Beauquier-Nivat; pseudo-square; pseudo-hexagon; enumeration of special classes of polyominoes},
language = {eng},
month = {7},
number = {2},
pages = {147-155},
publisher = {EDP Sciences},
title = {An algorithm for deciding if a polyomino tiles the plane},
url = {http://eudml.org/doc/250073},
volume = {41},
year = {2007},
}

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
DA - 2007/7//
PB - EDP Sciences
VL - 41
IS - 2
SP - 147
EP - 155
AB - 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.
LA - eng
KW - Polyominoes; tiling the plane by translation; theorem of Beauquier-Nivat; pseudo-square; pseudo-hexagon; enumeration of special classes of polyominoes
UR - http://eudml.org/doc/250073
ER -

References

top
  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.  Zbl0944.05005
  2. D. Beauquier and M. Nivat, On translating one polyomino to tile the plane. Discrete Comput. Geom.6 (1991) 575–592.  Zbl0754.05030
  3. M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons. Discrete Math.154 (1996) 1–25.  Zbl0858.05006
  4. M. Bousquet-Mélou. Habilitation. LABRI Université de Bordeaux 1 (1996).  
  5. S.J. Chang and K.Y. Lin. Rigorous results for the number of convex polygons on the square and honeycomb lattices. J. Phys. A21 (1988) 2635–2642.  
  6. T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to algorithms. Chapt. 34, MIT Press (1990) 853–885.  Zbl1158.68538
  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).  Zbl1115.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.  Zbl1032.05003
  9. M. Delest and X. Viennot, Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci.34 (1984) 169–206.  Zbl0985.68516
  10. I. Gambini, A Method for Cutting Squares Into Distinct Squares. Discrete Appl. Math.98 (1999) 65–80.  Zbl0935.05024
  11. S.W. Golomb. Polyominoes, Princeton science library (1994).  
  12. P. Hubert and L. Vuillon. Complexity of cutting words on regular tilings. Eur. J. Combin.28 (2007) 429–438.  Zbl1111.68095
  13. D.E. Knuth, J.H. Morris and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput.6 (1997) 323–350.  Zbl0372.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.  Zbl0921.05024
  15. P. Leroux and E. Rassart, Enumeration of symmetry classes of parallelogram polyminoes. Ann. Sci. Math. Québec25 (2001) 53–72.  Zbl1002.05015

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.