Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-18T09:08:51.600Z Has data issue: false hasContentIssue false
  • English
  • Français

An algorithm for deciding if a polyomino tiles the plane

Published online by Cambridge University Press:  18 July 2007

Ian Gambini  and
Laurent Vuillon
Ian Gambini
Affiliation:
Laboratoire d'Informatique Fondamentale de Marseille, CNRS UMR 6166, Université de la Méditerranée, 163 avenue de Luminy - Case 901, 13288 Marseille Cedex 9, France; [email protected]
Laurent Vuillon
Affiliation:
Laboratoire de Mathématiques, CNRS UMR 5127, Université de Savoie, 73376, le Bourget-du-Lac, France; [email protected]
Get access

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

Polyominoestiling the plane by translationtheorem of Beauquier-Nivatpseudo-squarepseudo-hexagonenumeration of special classes of polyominoes
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 2 , April 2007 , pp. 147 - 155
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barcucci, E., Del Lungo, A., Pergola, E. and Pinzani, R., ECO: a methodology for the Enumeration of Combinatorial Objects. J. Difference Equ. Appl. 5 (1999) 435–490. CrossRef
Beauquier, D. and Nivat, M., On translating one polyomino to tile the plane. Discrete Comput. Geom. 6 (1991) 575–592. CrossRef
Bousquet-Mélou, M., A method for the enumeration of various classes of column-convex polygons. Discrete Math. 154 (1996) 1–25. CrossRef
M. Bousquet-Mélou. Habilitation. LABRI Université de Bordeaux 1 (1996).
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.
T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to algorithms. Chapt. 34, MIT Press (1990) 853–885.
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).
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.
Delest, M. and Viennot, X., Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34 (1984) 169–206. CrossRef
Gambini, I., Method, A for Cutting Squares Into Distinct Squares. Discrete Appl. Math. 98 (1999) 65–80. CrossRef
S.W. Golomb. Polyominoes, Princeton science library (1994).
P. Hubert and L. Vuillon. Complexity of cutting words on regular tilings. Eur. J. Combin. 28 (2007) 429–438. CrossRef
Knuth, D.E., Morris, J.H. and Pratt, V.R.. Fast pattern matching in strings. SIAM J. Comput. 6 (1997) 323–350. CrossRef
Leroux, P., Rassart, E. and Robitaille, A., Enumeration of symmetry classes of convex polyminoes in the square lattice. Adv. Appl. Math. 21 (1998) 343–380. CrossRef
Leroux, P. and Rassart, E., Enumeration of symmetry classes of parallelogram polyminoes. Ann. Sci. Math. Québec 25 (2001) 53–72.