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