=Paper=
{{Paper
|id=Vol-3284/3328
|storemode=property
|title=On Counting k-Convex Polyominoes
|pdfUrl=https://ceur-ws.org/Vol-3284/3328.pdf
|volume=Vol-3284
|authors=Paolo Massazza
|dblpUrl=https://dblp.org/rec/conf/ictcs/Massazza22
}}
==On Counting k-Convex Polyominoes==
<pdf width="1500px">https://ceur-ws.org/Vol-3284/3328.pdf</pdf>
<pre>
On Counting k-Convex Polyominoes
(Short Paper)
Paolo Massazza1
1
    University of Insubria, Italy


                                         Abstract
                                         We show that, for any fixed integer 𝑘 > 2, the problem of computing the number of 𝑘-convex polyominoes
                                         of area 𝑛 is in P.

                                         Keywords
                                         polyominoes, counting problem, integer sequence




1. Introduction
A polyomino is a geometrical figure consisting of a finite set of connected unit squares (called
cells) in the plane Z × Z, considered up to translations. Polyominoes gained popularity after
the paper of S. W. Golomb [1]. Nowadays they are widely studied by physicists, mathemati-
cians, computer scientists and also by biologists. The problem of counting the number 𝑐𝑛 of
polyominoes with 𝑛 cells (i.e. of area 𝑛) is probably one of the fundamental open problems in
combinatorial geometry (see problem 37 in [2]). Due to the difficulty of the problem, simpler
classes of polyominoes have been introduced. In particular, the class of convex polyominoes
(polyominoes where the intersection with an infinite horizontal or vertical stripe is a finite
segment) and some of its subclasses have been investigated [3, 4, 5, 6, 7]. In this paper, we
consider the class Conv𝑘 [8] containing all convex polyominoes 𝑃 with the property that any
two cells of 𝑃 can be joined by a path in 𝑃 with at most 𝑘 changes of direction, where 𝑘 is a
fixed integer greater than 2. We show that, for any fixed 𝑘 > 2, the algorithm presented in [9]
leads to a set of recurrence equations for computing the number of 𝑘-convex polyominoes of
area 𝑛 in polynomial time, using 𝑂(𝑛5 ) space.


2. Notation and preliminaries
Let 𝑃 be a polyomino with an 𝑟 × 𝑐 minimal bounding rectangle. The rows (resp., columns) of
𝑃 are numbered from bottom to top (resp., from left to right). The area A(𝑃 ) of 𝑃 is the number
of its cells. A cell of 𝑃 is identified by a pair of integers (𝑖, 𝑗), where 𝑖 (resp., 𝑗) is the row
(resp., column) index. Two cells 𝑎 = (𝑖, 𝑗) and 𝑎′ = (𝑖′ , 𝑗 ′ ) are adjacent if |𝑖 − 𝑖′ | + |𝑗 − 𝑗 ′ | = 1.
Given two cells 𝑎 and 𝑏 of 𝑃 , a path in 𝑃 from 𝑎 to 𝑏 is a sequence 𝑞1 , 𝑞2 , . . . , 𝑞𝑘 of cells of
𝑃 , with 𝑞1 = 𝑎 and 𝑞𝑘 = 𝑏, such that 𝑞𝑖 and 𝑞𝑖+1 are adjacent for all 𝑖 with 1 ≤ 𝑖 < 𝑘. A
Proceedings of the 23rd Italian Conference on Theoretical Computer Science, Rome, Italy, September 7-9, 2022
" paolo.massazza@uninsubria.it (P. Massazza)
                                       © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
step is a sequence of two adjacent cells (𝑖, 𝑗), (𝑖′ , 𝑗 ′ ). Steps are distinguished according to the
directions N (North), W (West), S (South) and E (East). The number of changes of direction
in a path 𝛽 ∈ {N, W, S, E}+ is defined as the number of indices 𝑖 such that 𝛽𝑖 ̸= 𝛽𝑖+1 , with
1 ≤ 𝑖 < |𝛽|. A path is monotone if 𝛽 ∈ {N, W}+ (NW-path) or 𝛽 ∈ {N, E}+ (NE-path) or
𝛽 ∈ {S, E}+ (SE-path) or 𝛽 ∈ {S, W}+ (SW-path). A polyomino 𝑃 is horizontally convex (resp.,
vertically convex) if any row (resp. column) of 𝑃 consists of one segment. The class of convex
polyominoes contains all polyominoes that are both horizontally and vertically convex. It has
been proved [10, Proposition 1] that a polyomino 𝑃 is convex if and only if any two cells of
𝑃 are joined by a monotone path in 𝑃 . The degree of convexity of 𝑃 , denoted by deg𝑐 (𝑃 ),
is defined as the least integer 𝑘 such that any two cells of 𝑃 can be joined by a monotone
path in 𝑃 with at most 𝑘 changes of direction. A convex polyomino is called 𝑘-convex if its
degree of convexity is at most 𝑘. Given a convex polyomino 𝑃 and its minimal bounding
rectangle 𝐵, we say that 𝑃 is a stack (resp., Ferrers diagram, parallelogram, rectangle) if it shares
exactly two adjacent (resp., three, two opposite, four) vertices with 𝐵. A stack 𝑃 is a left (resp.,
right) stack if the column with the largest area is the last (resp., first) one. Analogously, in a
left (resp., right) Ferrers diagram the largest column is the last (resp., first) one. We denote
by L (resp., R) the set of left (resp., right) stacks. F𝐿 (resp., F𝑅 ) is the set of left (resp., right)
Ferrers diagrams. Furthermore, we indicate by C (resp., T) the set of parallelograms (resp.,
rectangles). For a class A of polyominoes, A(𝑛) is the set of polyominoes in A of area 𝑛. By
low(𝑗) (resp., high(𝑗)) we denote the row index of the bottom (resp., top) cell of column 𝑗.
Similarly, left(𝑖) denotes the column index of the leftmost cell of row 𝑖. Lastly, first(𝑃 )
(resp., last(𝑃 )) indicates the first (resp., last) column of 𝑃 . Given two columns 𝑖 and 𝑗, we
say that 𝑖 and 𝑗 are overlapping (resp., disjoint), denoted by 𝑖 𝑗 (resp., 𝑖 ≍ 𝑗), if and only if
                                                                    ⇄


low(𝑗) < low(𝑖) ≤ high(𝑗) < high(𝑖) or low(𝑖) < low(𝑗) ≤ high(𝑖) < high(𝑗) (resp.,
low(𝑖) > high(𝑗) or low(𝑗) > high(𝑖)). Moreover, we say that 𝑖 includes 𝑗, denoted by 𝑗 ⊆ 𝑖,
if and only if low(𝑖) ≤ low(𝑗) and high(𝑖) ≥ high(𝑗). Given a convex polyomino 𝑃 , let 𝑒
be the rightmost column of 𝑃 such that 𝑐 ⊆ 𝑒 for 1 ≤ 𝑐 < 𝑒. Then, 𝑃 is called descending
(resp., ascending) if there exists a column 𝑗 such that 𝑗 > 𝑒, 𝑗 𝑒 and low(𝑒) > low(𝑗) (resp.,
                                                                   ⇄




low(𝑒) < low(𝑗)). The set of descending (resp., ascending) 𝑘-convex polyominoes is indicated
by DConv𝑘 (resp., AConv𝑘 ). The set of all descening polyominoes is DConv. If 𝑃 is neither
descending nor ascending then 𝑃 ∈ T ∪ F𝐿 ∪ F𝑅 ∪ L ∪ R or it belongs to the class LR containing
all convex polyominoes that are the concatenation of two polyominoes, 𝑃 = 𝑃1 · 𝑃2 , where
𝑃1 ∈ L ∪ F𝐿 , 𝑃2 ∈ T ∪ R ∪ F𝑅 and first(𝑃2 ) ⊊ last(𝑃1 ). Notice that any 𝑃 ∈ LR contains
a column ¯𝚥 such that 𝑗 ⊆ ¯𝚥 for all columns 𝑗, hence deg𝑐 (𝑃 ) ≤ 2. Lastly, a cell (𝑖, 𝑗) of 𝑃 is
a NW-corner if (𝑖, 𝑗 − 1) and (𝑖 + 1, 𝑗) are not cells of 𝑃 . Analogously, we define NE-corners,
SE-corners and SW-corners. Two corners are called opposite if either one is a NW-corner and
the other is a SE-corner, or one is a NE-corner and the other is a SW-corner. Clearly, one
has Conv𝑘 = T ∪ F𝐿 ∪ F𝑅 ∪ L ∪ R ∪ LR ∪ AConv𝑘 ∪ DConv𝑘 and (because of symmetry)
|DConv𝑘 (𝑛)| = |AConv𝑘 (𝑛)|, |L(𝑛)| = |R(𝑛)|, |F𝐿 (𝑛)| = |F𝑅 (𝑛)|. Since all unions are disjoint,
it follows that
         |Conv𝑘 (𝑛)| = |T(𝑛)| + 2 · |F𝐿 (𝑛)| + 2 · |L(𝑛)| + |LR(𝑛)| + 2 · |DConv𝑘 (𝑛)|.             (1)
Thus, the counting problem for Conv𝑘 is reduced to computing |DConv𝑘 (𝑛)| and to some
other counting problems that are immediately solved in polynomial time. In particular, we can
                                  0                       0
                                      1                       1
                                          2                       2
                                              2   3   3               3   3
Figure 1: The arrows show the first steps of the paths determined by [9, Lemma 8] and associated with
a SW corner. The integer below a column indicates its degree of convexity.


compute |LR(𝑛)| in polynomial time as shown in [11]. In order to compute |DConv𝑘 (𝑛)| we
define a decomposition for descending polyominoes.

Definition 2.1 (standard decomposition). A polyomino 𝑃 ∈ DConv can be decomposed as
𝑃 = 𝐿 · 𝐹 · 𝐶 · 𝑅 (with 𝐹 , 𝑅 possibly empty) for suitable polyominoes 𝐿 ∈ L ∪ T ∪ F𝐿 , 𝐹 ∈ F𝑅 ,
𝐶 ∈ C ∪ T ∪ F𝑅 , and 𝑅 ∈ R ∪ T ∪ F𝑅 such that: first(𝐹 ) ⊊ last(𝐿), low(last(𝐿)) =
low(first(𝐹 )), last(𝐹 ) first(𝐶) (or last(𝐿) first(𝐶) if 𝐹 = 𝜖), low(last(𝐿)) >
                            ⇄




                                                          ⇄
low(first(𝐶)) and (if 𝑅 ̸= 𝜖) first(𝑅) ⊊ last(𝐶), low(last(𝐶)) < low(first(𝑅)).

    We stress that the standard decomposition of 𝑃 is unique (e.g. last(𝐿) is the rightmost
column ¯𝚥 of 𝑃 such that 𝑗 ⊆ ¯𝚥 for 𝑗 < ¯𝚥). The subset of DConv2 containing polyominoes
decomposed as 𝐿 · 𝐶 · 𝑅 (resp., 𝐿 · 𝐶, 𝐿 · 𝐹 · 𝐶 · 𝑅, 𝐿 · 𝐹 · 𝐶) is LCR2 (resp., LC2 , LFCR2 , LFC2 ).
Thus, for any 𝑘 > 2 one has the partition DConv𝑘 = LFCR𝑘 ∪ LFC𝑘 ∪ LCR𝑘 ∪ LC𝑘 .
    By [9, Thm. 6], the degree of convexity of 𝑃 ∈ DConv depends on the number 𝑘 of changes
of direction in a particular NW-path that starts at a SE-corner 𝑎 and ends at a NW-corner 𝑏. This
is a path where the first 𝑘 − 1 changes of direction always occur on the boundary of 𝑃 , whereas
the 𝑘th one possibly occurs on a cell that is not on the boundary. Furthermore, from [9, Thm. 6]
it follows that the degree of convexity of the 𝑗th column of 𝑃 is deg𝑐 (𝑃, 𝑗) = max{𝐷(𝑎, 𝑏)|𝑎 =
(low(𝑗) , 𝑗), 𝑏 is a NW-corner of 𝑃 }, where 𝐷(𝑎, 𝑏), is the least integer k such that there exists
a monotone path in 𝑃 from 𝑎 to 𝑏 with k changes of direction.
    Given 𝑃 = 𝐿 · 𝐹 · 𝐶 · 𝑅 and a column 𝑗 in 𝐹 · 𝐶 · 𝑅, we know from [9, Lemma 8]
that deg𝑐 (𝑃, 𝑗) = min(deg𝑐 (𝑃, 𝑗 ′ ) + 2, deg𝑐 (𝑃, 𝑗 ′′ ) + 1), where 𝑗 ′ = left(high(𝑗)) and
𝑗 ′′ = left(low(𝑗)). see Fig. 1 for an example. In the sequel, we consider each column 𝑐 of 𝑃
as the concatenation of vertical segments associated with different degrees of convexity. These
segments are identified by considering the degrees of convexity of the leftmost columns that
are reached by W-paths starting from cells of 𝑐.

Definition 2.2 (𝛽-segment). A cell (𝑖, 𝑗) of 𝑃 ∈ DConv belongs to a 𝛽-segment if and only if
either 𝛽 > 0 ∧ 𝑖 < low(first(𝑃 )) and the cell (𝑖, left(𝑖)) belongs to a column of degree of
convexity 𝛽, or 𝛽 = 0 ∧ 𝑖 ≥ low(first(𝑃 )).

   From [9, Lemma 8], if deg𝑐 (𝑃, 𝑗) = 𝛼 then column 𝑗 may contain only 𝛽-segments with
𝛼 − 2 ≤ 𝛽 ≤ 𝛼. Notice that (𝑖, 𝑗) belongs to a 𝛽-segment if and only if (𝑖, 𝑗 − 1) belongs
to a 𝛽-segment or (𝑖, 𝑗 − 1) is not in 𝑃 and deg𝑐 (𝑃, 𝑗) = 𝛽. Fig. 1 shows how the columns
of a polyomino in DConv consist of at most three 𝛽-segments (depicted as vertical segments
comprising cells of the same color).
Figure 2: A polyomino counted by 𝐶(16, 5, 3, 3, 1, 2).


3. Counting
We focus on computing |DConv𝑘 (𝑛)| since the remaining values in (1) are easily computed
in polynomial time (see, for instance, [11]). Given 𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖 ∈ N, with 𝑛, 𝑏 > 0 and
𝑥 + 𝑦 ≤ 𝑏, let 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖) be the number of polyominoes 𝑃 in LFC𝑘 (𝑛) ∪ LC𝑘 (𝑛) such that
A(last(𝑃 )) = 𝑏, deg𝑐 (𝑃, last(𝑃 )) = 𝑗, low(last(𝑃 ) − 1) − low(last(𝑃 )) = 𝑖, and where
last(𝑃 ) contains a 𝑗-segment of area 𝑥, a (𝑗 − 1)-segment of area 𝑦∑︀and a (𝑗 − 2)-segment of
area 𝑏−𝑥−𝑦, see Fig. 2. Obviously, one has |LFC𝑘 (𝑛)|+|LC𝑘 (𝑛)| = 𝑏,𝑗,𝑥,𝑦,𝑖 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖),
and the problem boils down to compute 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖) efficiently.
    Consider the standard decomposition of a polyomino 𝑃 counted by 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖), 𝑃 =
𝐿 · 𝐹 · 𝐶 or 𝑃 = 𝐿 · 𝐶. If the second to last column of 𝑃 belongs to 𝐶 then 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖)
depends on 𝐶(𝑛 − 𝑏, 𝑏′ , 𝑗 ′ , 𝑥′ , 𝑦 ′ , 𝑖′ ) for suitable 𝑏′ , 𝑗 ′ , 𝑥′ , 𝑦 ′ , 𝑖′ . Otherwise, the second to last
column of 𝑃 is in 𝐹 or in 𝐿, and 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖) is computed using the values 𝐿(𝑚′ , 𝑝′ , 𝑞 ′ , 𝑦 ′ )
and 𝐹 (𝑚′ , 𝑝′ , 𝑞 ′ ), where 𝐿(𝑚′ , 𝑝′ , 𝑞 ′ , 𝑦 ′ ) (resp., 𝐹 (𝑚′ , 𝑝′ , 𝑞 ′ )) is the number of 𝑃 ∈ L(𝑚′ ) ∪
F𝐿 (𝑚′ ) ∪ T(𝑚′ ) (resp. 𝑃 ∈ F𝑅 (𝑚′ )) such that A(first(𝑃 )) = 𝑝′ , A(last(𝑃 )) = 𝑞 ′ and
low(first(𝑃 ))−low(last(𝑃 )) = 𝑦 ′ . Here we consider only the case when column last(𝑃 )−
1 is in 𝐶 (we refer to the full paper for the remaining cases). This is the most complex case
as it leads to four different equations, depending on the conditions 𝑥 > 𝑖 (1), 𝑥 = 𝑖 ∧ 𝑦 = 0
(2), 𝑥 = 𝑖 ∧ 𝑦 > 0 ∧ 𝑖 > 0 (3) and 𝑥 = 𝑖 ∧ 𝑦 > 0 ∧ 𝑖 = 0 (4). In case (1), column last(𝑃 ) − 1
always has degree of convexity 𝑗, since the relation 𝑥 > 𝑖 implies the existence of a column
of degree of convexity 𝑗 to the left of last(𝑃 ), and the sequence of degrees of convexity of
columns in 𝐶 is not decreasing by [9, Thm. 9]. Furthermore, one necessarily has 𝑥 + 𝑦 < 𝑏
because
∑︀𝑛−𝑏−2last(𝑃  ∑︀𝑥−𝑖 ) contains ′a (𝑗 − 2)-segment,             see Fig. 3. So, it follows that 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖) =
                      𝐶(𝑛 −    𝑏, 𝑏 , 𝑗, 𝑥 −   𝑖, 𝑦, 𝑖 ′ ). In case (3) (see Fig. 4) the recurrence equation is
      ′
     𝑏 =𝑏−𝑖       ′
                 𝑖 =0
                                         ∑︀𝑏′ −𝑏+𝑖−1 ∑︀𝑦
𝐶(𝑛, 𝑏, 𝑗, 𝑖, 𝑦, 𝑖) = 𝑛−𝑏−2
                         ∑︀                                                   ′              ′ ′
                                                                                                    ∑︀𝑛−𝑏−2
                            𝑏′ =𝑏−𝑖+1      𝑦 ′ =𝑏−𝑖−𝑦        𝑖′ =0 𝐶(𝑛 − 𝑏, 𝑏 , 𝑗 − 1, 𝑦, 𝑦 , 𝑖 ) +    𝑏′ =𝑏−𝑖 𝐶(𝑛 −
𝑏, 𝑏 , 𝑗, 0, 𝑦, 0). In fact, the second to last column of a polyomino 𝑃 counted by 𝐶(𝑛, 𝑏, 𝑗, 𝑖, 𝑦, 𝑖)
      ′

may have degree of convexity 𝑗 −1 or 𝑗, but not 𝑗 −2. Indeed, if one had deg𝑐 (𝑃, last(𝑃 )−1) =
𝑗−2 then the sequence of degrees of convexity in 𝐶 would be decreasing, since last(𝑃 ) contains
a (𝑗 − 1)-segment and this implies the existence of a column 𝑚 to the left of last(𝑃 ) such
that deg𝑐 (𝑃, 𝑚) = 𝑗 − 1. Furthermore, 𝑥 = 𝑖 ∧ 𝑖 > 0 implies that last(𝑃 ) contains a (𝑗 − 2)-
segment. As a consequence the (𝑗 − 1)-segments in last(𝑃 ) − 1 and in last(𝑃 ) have the same
area. So, if deg𝑐 (𝑃, last(𝑃 ) − 1) = 𝑗 − 1 we sum the values 𝐶(𝑛 − 𝑏, 𝑏′ , 𝑗 − 1, 𝑦, 𝑦 ′ , 𝑖′ ) on all
𝑏′ , 𝑦 ′ , 𝑖′ such that:
Figure 3: Possible configurations when 𝑥 > 𝑖.




Figure 4: Possible configurations when 𝑥 = 𝑖 and 𝑥, 𝑦 > 0.


    • the area 𝑏′ of column last(𝑃 ) − 1 is at least 𝑏 − 𝑖 + 1 (since 𝑏′ must contain a (𝑗 − 3)-
      segment) and at most 𝑛 − 𝑏 − 2 (since A(𝐿) ≥ 2);
    • the area 𝑦 ′ of the (𝑗 − 2)-segment in last(𝑃 ) − 1 is at least 𝑏 − 𝑖 − 𝑦 (the area of the
      (𝑗 − 2)-segment in last(𝑃 )) and at most 𝑏′ − 𝑏 + 𝑖 − 1 (because column last(𝑃 ) − 1
      must contain a (𝑗 − 3)-segment);
    • 𝑖′ is at least 0 and at most 𝑦 (the lower 𝑖′ cells of last(𝑃 ) − 1 has degree 𝑗 − 1 since
      left(low(last(𝑃 ) − 1) + 𝑒) = last(𝑃 ) − 1 for 0 ≤ 𝑒 < 𝑖′ ).
Otherwise, if deg𝑐 (𝑃, last(𝑃 ) − 1) = 𝑗 we sum the values 𝐶(𝑛 − 𝑏, 𝑏′ , 𝑗, 0, 𝑦, 0) on all 𝑏′ no
smaller than 𝑏 − 𝑖 and no greater than 𝑛 − 𝑏 − 2. From the existence of a (𝑗 − 1)-segment in
last(𝑃 ) and deg𝑐 (𝑃, last(𝑃 )−1) = 𝑗, it follows low(last(𝑃 ) − 2)−low(last(𝑃 ) − 1) = 0.
Hence, last(𝑃 ) − 1 cannot contain a 𝑗-segment. The recurrence equations for cases (2) and
(4), as well as for the cases associated with the set LCR𝑘 ∪ LFCR𝑘 , are obtained by a similar
reasoning.
   Based on these equations, we have developed a C++ program to compute |Conv𝑘 (𝑛)| for
𝑘 > 2 and 𝑛 > 0. This program has space complexity 𝑂(𝑛5 ) (coming from the size of the table
containing the values 𝐶(𝑛, 𝑏, 𝑗, 𝑥, 𝑦, 𝑖)) and produced Table 1 in few minutes (on a Macbook
Pro). We point out that this integer sequence does not appear in OEIS.


References
 [1] S. W. Golomb, Checker boards and polyominoes, Amer. Math. Monthly 61 (1954) 675–682.
 [2] E. D. Demaine, J. S. B. Mitchell, J. O’Rourke, The open problems project, last update 2020.
     URL: http://cs.smith.edu/~jorourke/TOPP.
Table 1
The number of 3-convex polyominoes of area 𝑛 for 0 ≤ 𝑛 ≤ 40.
   0, 1, 2, 6, 19, 59, 172, 470, 1206, 2934, 6812, 15192, 32709, 68282, 138678, 274822, 532719, 1012144
      1888226, 3464168, 6258249, 11146013, 19590450, 34011064, 58371083, 99103808, 166563604,
          277281796, 457451501, 748274488, 1214117566, 1954879052, 3124637754, 4959621329,
   7819943680, 12251575214, 19077932142, 29534613958, 45466767846, 69616951878, 106043316448


 [3] M. Bousquet-Mélou, Convex polyominoes and heaps of segments, Journal of Physics A:
     Mathematical and General 25 (1992) 1925–1934. URL: https://doi.org/10.1088/0305-4470/
     25/7/031. doi:10.1088/0305-4470/25/7/031.
 [4] E. Barcucci, R. Pinzani, R. Sprugnoli, Directed column-convex polyominoes by recurrence
     relations, in: M. C. Gaudel, J. P. Jouannaud (Eds.), TAPSOFT’93: Theory and Practice of
     Software Development, Springer Berlin Heidelberg, Berlin, Heidelberg, 1993, pp. 282–298.
 [5] M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex
     polygons., Discrete Math. 154 (1996) 1–25.
 [6] A. Del Lungo, M. Nivat, R. Pinzani, S. Rinaldi, A bijection for the total area of parallelogram
     polyominoes, Discret. Appl. Math. 144 (2004) 291–302. URL: https://doi.org/10.1016/j.dam.
     2003.11.007. doi:10.1016/j.dam.2003.11.007.
 [7] G. Castiglione, A. Restivo, Ordering and convex polyominoes, in: MCU 2004, volume 3354
     of Lecture Notes in Comput. Sci., Springer, 2005, pp. 128–139.
 [8] A. Micheli, D. Rossin, Counting k-convex polyominoes, Electron. J. Comb. 20 (2013).
 [9] S. Brocchi, G. Castiglione, P. Massazza, On the exhaustive generation of k-convex poly-
     ominoes, Theor. Comput. Sci. 664 (2017) 54–66.
[10] G. Castiglione, A. Restivo, Reconstruction of l-convex polyominoes, Electronic Notes in Dis-
     crete Mathematics 12 (2003) 290 – 301. URL: http://www.sciencedirect.com/science/article/
     pii/S1571065304004949. doi:https://doi.org/10.1016/S1571-0653(04)00494-9,
     9th International Workshop on Combinatorial Image Analysis.
[11] V. Dorigatti, P. Massazza, On counting l-convex polyominoes, in: 22nd Italian Conference
     on Theoretical Computer Science, 2021, volume 3072 of CEUR Proceedings, 2021, pp. 193–
     198.

</pre>