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, SIMONE
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.
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/46093
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo