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