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 $\cal{F}(\pi)$ on the points of π, and prove that there exists a column-convex permutomino P such that π1 (P) = π if and only if $\cal{F}(\pi)$ is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1 (P) = π.

Bilotta, S., Rinaldi, S., Socci, S. (2013). Polygons drawn from a permutation. FUNDAMENTA INFORMATICAE, 125(3-4), 329-342 [10.3233/FI-2013-867].

### Polygons drawn from a permutation

#### 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 $\cal{F}(\pi)$ on the points of π, and prove that there exists a column-convex permutomino P such that π1 (P) = π if and only if $\cal{F}(\pi)$ is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1 (P) = π.
##### Scheda breve Scheda completa Scheda completa (DC)
2013
Bilotta, S., Rinaldi, S., Socci, S. (2013). Polygons drawn from a permutation. FUNDAMENTA INFORMATICAE, 125(3-4), 329-342 [10.3233/FI-2013-867].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/46068