Generation of Skew Convex Polyominoes

We study the family of skew polyominoes, an intermediate class between 𝐿-convex and 4-stack polyominoes, defined by geometrical constraints satisfied by pairs of rows/columns. The problem of enumerating this family according to the semi-perimeter (size) is open, and can lead to a simplified enumeration of 𝑍-convex polyominoes. We define a recursive method for the exhaustive generation of these objects of given size, based on generating trees. In practice, we introduce a set of operations on skew polyominoes, which perform local expansions on the objects, and such that every skew polyomino of size 𝑛 + 1 is uniquely generated from one of size 𝑛. This leads to a simple algorithm for the exhaustive generation of skew polyominoes of size 𝑛 in constant amortized time.