In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π1, π2). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π1(P) = π or π2(P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications F(p) on the points of π, and prove that there exists a column-convex permutomino P such that π1(P) = π if and only if F(p) is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1(P) = π.
Polygons Drawn from Permutations / Stefano Bilotta; Simone Rinaldi; Samata Socci. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - STAMPA. - 125:(2013), pp. 329-342. [10.3233/FI-2013-867]
Polygons Drawn from Permutations
BILOTTA, STEFANO;
2013
Abstract
In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π1, π2). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π1(P) = π or π2(P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications F(p) on the points of π, and prove that there exists a column-convex permutomino P such that π1(P) = π if and only if F(p) is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1(P) = π.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.