A polyomino is said to be L-convex if any two of its cells can be connected by a path entirely contained in the polyomino, and having at most one change of direction. In this paper, answering a problem posed by Castiglione and Vaglica [6], we prove that the class of L-convex polyominoes is tiling recognizable. To reach this goal, first we express the L-convexity constraint in terms of a set of independent properties, then we show that each class of convex polyominoes having one of these properties is tiling recognizable.
Brocchi, S., Frosini, A., Pinzani, R., Rinaldi, S. (2013). A tiling system for L-convex polyominoes. THEORETICAL COMPUTER SCIENCE, 475, 73-81 [10.1016/j.tcs.2012.12.033].
A tiling system for L-convex polyominoes
Rinaldi S.
2013-01-01
Abstract
A polyomino is said to be L-convex if any two of its cells can be connected by a path entirely contained in the polyomino, and having at most one change of direction. In this paper, answering a problem posed by Castiglione and Vaglica [6], we prove that the class of L-convex polyominoes is tiling recognizable. To reach this goal, first we express the L-convexity constraint in terms of a set of independent properties, then we show that each class of convex polyominoes having one of these properties is tiling recognizable.
| File | Dimensione | Formato | |
|---|---|---|---|
|
L-convex_recog.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
513.02 kB
Formato
Adobe PDF
|
513.02 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/46093
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo