In this paper we explore the connections between two classes of polyominoes, namely the permutominoes and the pseudo-square polyominoes. A permutomino is a polyomino uniquely determined by a pair of permutations. Permutominoes, and in particular convex permutominoes, have been considered in various kinds of problems such as: enumeration, tomographical reconstruction, and algebraic characterization. On the other hand, pseudo-square polyominoes are a class of polyominoes tiling the plane by translation. The characterization of such objects has been given by Beauquier and Nivat, who proved that a polyomino tiles the plane by translation if and only if it is a pseudo-square or a pseudo-hexagon. In particular, a polyomino is pseudo-square if its boundary word may be factorized as XYX̂, where Xî denotes the path X traveled in the opposite direction. In this paper we relate the two concepts by considering the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed X, each word Y such that XYX̂ is pseudo-square is prefix of a unique infinite word Y with period 4|X|N|X|E. Also, we show that XYX̂ are centrosymmetric, i.e. they are fixed by rotation of angle π. The proof of this fact is based on the concept of pseudoperiods, a natural generalization of periods. © 2012 Elsevier B.V. All rights reserved.
Frosini, A., Blondin Massè, A., Rinaldi, S., Vuillon, L. (2013). The shape of permutominoes tiling the plane. DISCRETE APPLIED MATHEMATICS, 161(15), 2316-2327 [10.1016/j.dam.2012.08.034].
The shape of permutominoes tiling the plane
Rinaldi S.;
2013-01-01
Abstract
In this paper we explore the connections between two classes of polyominoes, namely the permutominoes and the pseudo-square polyominoes. A permutomino is a polyomino uniquely determined by a pair of permutations. Permutominoes, and in particular convex permutominoes, have been considered in various kinds of problems such as: enumeration, tomographical reconstruction, and algebraic characterization. On the other hand, pseudo-square polyominoes are a class of polyominoes tiling the plane by translation. The characterization of such objects has been given by Beauquier and Nivat, who proved that a polyomino tiles the plane by translation if and only if it is a pseudo-square or a pseudo-hexagon. In particular, a polyomino is pseudo-square if its boundary word may be factorized as XYX̂, where Xî denotes the path X traveled in the opposite direction. In this paper we relate the two concepts by considering the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed X, each word Y such that XYX̂ is pseudo-square is prefix of a unique infinite word Y with period 4|X|N|X|E. Also, we show that XYX̂ are centrosymmetric, i.e. they are fixed by rotation of angle π. The proof of this fact is based on the concept of pseudoperiods, a natural generalization of periods. © 2012 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
perm_tiles.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
276.53 kB
Formato
Adobe PDF
|
276.53 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/46104
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo