Polygons Drawn from Permutations

Abstract

In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π₁, π₂). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π₁(P) = π or π₂(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 π₁(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 π₁(P) = π.