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

A tiling system for the class of L-convex polyominoes / S. Brocchi; A. Frosini; R. Pinzani; S. Rinaldi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - (2013), pp. 73-81. [10.1016/j.tcs.2012.12.033]

A tiling system for the class of L-convex polyominoes

BROCCHI, STEFANO;FROSINI, ANDREA;PINZANI, RENZO;
2013

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, 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
73
81
S. Brocchi; A. Frosini; R. Pinzani; S. Rinaldi
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397512011486-main.pdf

Accesso chiuso

Tipologia: Altro
Licenza: Tutti i diritti riservati
Dimensione 513.02 kB
Formato Adobe PDF
513.02 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/794168
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact