1. Introduction

The present paper uses the theoretical material developed in a previous study by the authors in order to reconstruct a subclass of 2-convex polyominoes. Indeed, 2-convex polyominoes are the first difficult class of polyominoes in terms of tomographical reconstruction in the hierarchy of k-polyominoes and in this article we design an algorithm of reconstruction for a subclass of L-convex which is the second step in the whole comprehension of the hierarchy of k-polyominoes.

One main problem in discrete tomography consists on the reconstruction of discrete objects according to their horizontal and vertical projection vectors. In order to restrain the number of solutions, we could add convexity constraints to these discrete objects. There are many notions of discrete convexity of polyominoes (namely HV-convex [1] , Q-convex [2] , L-convex polyominoes [3] ) and each one leads to interesting studies. One natural notion of convexity on the discrete plane is the class of HV-convex polyominoes that are polyominoes with consecutive cells in rows and columns. Following the work of Del Lungo, Nivat, Barcucci, and Pinzani [1] we are able using discrete tomography to reconstruct polyominoes that are HV-convex according to their horizontal and vertical projections. In addition to that, for an HV-convex polyomino P every pairs of cells of P can be reached using a path included in P with only two kinds of unit steps (such a path is called monotone). A polyomino is called k-convex if for every two cells we find a monotone path with at most k changes of direction. Obviously a k-convex polyomino is an HV-convex polyomino. Thus, the set of k-convex polyominoes for $k\in \mathbb{N}$ forms a hierarchy of HV-convex polyominoes according to the number of changes of direction of monotone paths. This notion of 1-convex polyominoes has been considered by several points of view. In [4] combinatorial aspects of 1-convex polyominoes are analyzed, giving the enumeration according to the semi-perimeter and the area. In [5] it is given an algorithm that reconstructs a 1-convex polyomino from the set of its maximal L-polyominoes. Similarly in [3] it is given another way to reconstruct a L-convex polyomino from the size of some special paths, called bordered L-paths.

In fact 2-convex polymoninoes are more geometrically complex and there was no result for their direct reconstruction. We could notice that Duchi, Rinaldi, and Schaeffer are able to enumerate this class in an interesting and technical article [6] . But the enumeration technique gives no idea for the tomographical reconstruction.

The first subclass that creates the link with 2-convex polyominoes is the class of HV-centered polyominoes. In [7] , it is showed that if P is an HV-centered polyomino then P is 2-convex. Note that the tomographical properties of this subclass have been studied in [8] and its reconstruction algorithm is well known.

The main contribution of this paper is an $O\left(m^3{n}^3\right)$ -time algorithm for reconstructing a subclass of 2-convex polyominoes using the geometrical properties studied in a previous study, and the algorithm of Chrobak and Dürr [8] . In particular, we add well-chosen clauses to the original construction of Chrobak and Dürr in order to control the 2L-convexity using 2SAT satisfaction problem.

This paper is divided into 5 sections. After basics on polyominoes, Section 3 shows the different geometrical shapes of a subclass of 2-convex polyominoes [9] . In Section 4, the algorithm of Chrobak and Dürr for the reconstruction of the HV-convex polyominoes is given [8] . Section 5 describes the reconstruction of different subclasses of 2-convex polyominoes.

2. Definition and Notation

A planar discrete set is a finite subset of the integer lattice ${\mathbb{Z}}^2$ defined up to translation. A discrete set can be represented either by a set of cells, i.e. unitary squares of the cartesian plane, or by a binary matrix, where the 1’s determine the cells of the set (see Figure 1).

A polyomino P is a finite connected set of adjacent cells, defined up to translations, in the cartesian plane. A row convex polyomino (resp. column-convex) is

a self avoiding convex polyomino such that the intersection of any horizontal line (resp. vertical line) with the polyomino has at most two connected components. Finally, a polyomino is said to be convex (or HV-convex) if it is both row and column-convex (see Figure 2).

To each discrete set S, represented as a $m\times n$ binary matrix, two integer vectors $H=\left(h_1,\cdots ,h_m\right)$ and $V=\left(v_1,\cdots ,v_n\right)$ are associated such that, for each $1\le i\le m\mathrm{,1}\le j\le n$, $h_i$ and $v_j$ are the number of cells of S (elements 1 of the matrix) which lie on row i and column j, respectively. The vectors H and V are called the horizontal and vertical projections of S, respectively (see Figure 3). Moreover if S has H and V as horizontal and vertival projections, respectively, then we say that S satisfies (H, V). Using the usual matrix notations, the element $\mathrm{<mo\; stretchy="false">\; (\; </mo>}i\mathrm{,}j\mathrm{<mo\; stretchy="false">\; )\; </mo>}$ denotes the entry in row i and column j.

For any two cells A and B in a polyomino, a path ${\Pi }_{AB}$, from A to B, is a sequence $\left(i_1\mathrm{,}{j}_1\right)\mathrm{,}\left(i_2\mathrm{,}{j}_2\right)\mathrm{,}\cdots \mathrm{,}\left(i_r\mathrm{,}{j}_r\right)$ of adjacent disjoint cells belonging in P, with $A=\left(i_1,j_1\right)$, and $B=\left(i_r,j_r\right)$. For each $1\le k\le r-1$, we say that the two consecutive cells $\left(i_k\mathrm{,}{j}_k\right)\mathrm{,}\left(i_{k+1}\mathrm{,}{j}_{k+1}\right)$ form:

• an east step if $i_{k+1}=i_k$ and $j_{k+1}=j_k+1$ ;

• a north step if $i_{k+1}=i_k-1$ and $j_{k+1}=j_k$ ;

• a west step if $i_{k+1}=i_k$ and $j_{k+1}=j_k-1$ ;

• a south step if $i_{k+1}=i_k+1$ and $j_{k+1}=j_k$.

Finally, we define a path to be monotone if it is entirely made of only two of the four types of steps defined above (see [7] [10] ).

Proposition 1 (Castiglione, Restivo). A polyomino P is HV-convex if and only if every pair of cells is connected by a monotone path.

Let us consider a polyomino P. A path in P has a change of direction in the cell $\left(i_k\mathrm{,}{j}_k\right)$, for $2\le k\le r-1$, if

$i_k\ne i_{k-1}\iff j_{k+1}\ne j_k\mathrm{.}$

Definition 1. We call k-convex an HV-convex polyomino such that every pair of its cells can be connected by a monotone path with at most k changes of direction respectively.

In [5] , it is proposed a hierarchy on convex polyominoes based on the number of changes of direction in the paths connecting any two cells of a polyomino.

For $k=1$, we have the first level of hierarchy, i.e. the class of 1-convex polyominoes, also denoted L-convex polyominoes for the typical shape of each

path having at most one single change of direction. In the present study, we focus our attention on the next level of the hierarchy, i.e. the class of 2-convex polyominoes, whose geometrical properties are more complicated and harder to be investigated than those of 1-convex polyominoes (see Figure 4).

3. 2-Convex Polyominoes

Let $\left(H\mathrm{,}V\right)$ be two projection vectors and let P be an HV-convex polyomino, that satisfies $\left(H\mathrm{,}V\right)$. By a classical argument P is contained in a rectangle R (called minimal bounding box) where in this box no projection gives a zero. Let $\left[\min \left(S\right)\mathrm{,}\max \left(S\right)\right]$ ( $\left[\min \left(E\right)\mathrm{,}\max \left(E\right)\right]$,#Math_41#, $\left[\min \left(W\right)\mathrm{,}\max \left(W\right)\right]$ ) be the intersection of P’s boundary on the lower (right, upper, left) side of R (see [1] ). By abuse of notation, we call $\min \left(S\right)$ [resp. $\min \left(E\right)$, $\min \left(N\right)$, $\min \left(W\right)$ ] the cell at the position $\left(m\mathrm{,}\min \left(S\right)\right)$ [resp. $\left(\min \left(E\right)\mathrm{,}n\right)$, $\left(\mathrm{1,}\min \left(N\right)\right)$, $\left(\min \left(W\right)\mathrm{,1}\right)$ ] and $\max \left(S\right)$ [resp. $\max \left(E\right)$, $\max \left(N\right)$, $\max \left(W\right)$ ] the cell at the position $\left(m\mathrm{,}\max \left(S\right)\right)$ [resp. $\left(\max \left(E\right)\mathrm{,}n\right)$, $\left(\mathrm{1,}\max \left(N\right)\right)$, $\left(\max \left(W\right)\mathrm{,1}\right)$ ] (see Figure 5).

Definition 2. The segment $\left[\min \left(S\right)\mathrm{,}\max \left(S\right)\right]$ is called the S-foot. Similarly, the segments $\left[\min \left(E\right)\mathrm{,}\max \left(E\right)\right]$, $\left[\min \left(N\right)\mathrm{,}\max \left(N\right)\right]$ and $\left[\min \left(W\right)\mathrm{,}\max \left(W\right)\right]$ are called E-foot, N-foot and W-foot.

For a bounding rectangle R and for a given polyomino P, let us define the following sets:

• $WN=\left\{\left(i,j\right)\in P|i<\min \left(W\right)\text{and}j<\min \left(N\right)\right\}$,

• $SE=\left\{\left(i,j\right)\in P|i>\max \left(E\right)\text{and}j>\max \left(S\right)\right\}$,

• $NE=\left\{\left(i,j\right)\in P|i<\min \left(E\right)\text{and}j>\max \left(N\right)\right\}$,

• $WS=\left\{\left(i,j\right)\in P|i>\max \left(W\right)\text{and}j<\min \left(S\right)\right\}$.

Let $\mathcal{C}$ be the class of HV-convex polyominoes, thus we have the following classes of polyominoes regarding the position of the non-intersecting feet.

• $\begin{array}{l}{\alpha }^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=1\text{and}card\left(SE\right)=1\}\end{array}$,

• $\begin{array}{l}{\beta }^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(S\right)<\min \left(N\right)\text{and}\max \left(E\right)<\min \left(W\right);\\ card\left(NE\right)=1\text{and}card\left(WS\right)=1\}\end{array}$,

• $\begin{array}{l}{\alpha }_{2L}^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min (\left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=1\text{and}card\left(SE\right)=1\}\end{array}$, where P is a 2-convex polyomino.

• $\begin{array}{l}{\beta }_{2L}^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(S\right)<\min \left(N\right)\text{and}\max \left(E\right)<\min \left(W\right);\\ card\left(NE\right)=1\text{and}card\left(WS\right)=1\}\end{array}$, where P is a 2-convex polyomino.

Now in order to understand the different geometries of the class ${\alpha }_{2L}^{\mathrm{1,1}}$, let us define the following subclasses of the class ${\alpha }^{\mathrm{1,1}}$.

• $\begin{array}{l}{\gamma }^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);card\left(WN\right)=1\\ \text{and}card\left(SE\right)=1;\min \left(E\right)=\max \left(W\right)+1\text{and}\min \left(S\right)=\max \left(N\right)+1\}\end{array}$ (see Figure 6).

• $\begin{array}{l}{\delta }^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(S\right)<\min \left(N\right)\text{and}\max \left(E\right)<\min \left(W\right);card\left(NE\right)=\mathrm{1\; <mi>\; </mi>}\\ \text{and}card\left(WS\right)=1;\min \left(E\right)\ne \max \left(W\right)+1\text{and}\min \left(S\right)=\max \left(N\right)+1\}\end{array}$. (see Figure 6).

• $\begin{array}{l}{\Delta }^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);card\left(WN\right)=1\\ \text{and}card\left(SE\right)=1;\min \left(E\right)=\max \left(W\right)+1\text{and}\min \left(S\right)\ne \max \left(N\right)+1\}\end{array}$ (see Figure 6).

• $\begin{array}{l}{\chi }^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);card\left(WN\right)=1\\ \text{and}card\left(SE\right)=1;\min \left(E\right)\ne \max \left(W\right)+1\text{and}\min \left(S\right)\ne \max \left(N\right)+1\}\end{array}$ (see Figure 6).

• $\begin{array}{l}{\gamma }_{2L}^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);card\left(WN\right)=1\\ \text{and}card\left(SE\right)=1;\min \left(E\right)=\max \left(W\right)+1\text{and}\min \left(S\right)=\max \left(N\right)+1\}\end{array}$, where P is a 2-convex polyomino.

• $\begin{array}{l}{\delta }_{2L}^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(S\right)<\min \left(N\right)\text{and}\max \left(E\right)<\min \left(W\right);card\left(NE\right)=1\\ \text{and}card\left(WS\right)=1;\min \left(E\right)\ne \max \left(W\right)+1\text{and}\min \left(S\right)=\max \left(N\right)+1\}\end{array}$, where P is a 2-convex polyomino.

• $\begin{array}{l}{\Delta }_{2L}^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);card\left(WN\right)=1\\ \text{and}card\left(SE\right)=1;\min \left(E\right)=\max \left(W\right)+1\text{and}\min \left(S\right)\ne \max \left(N\right)+1\}\end{array}$, where P is a 2-convex polyomino.

• $\begin{array}{l}{\chi }_{2L}^{1,1}=\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\text{and}\max \left(W\right)<\min \left(E\right);card\left(WN\right)=1\\ \text{and}card\left(SE\right)=1;\min \left(E\right)\ne \max \left(W\right)+1\text{and}\min \left(S\right)\ne \max \left(N\right)+1\}\end{array}$, where P is a 2-convex polyomino.

Theorem 1. Let P be a convex polyomino in the class ${\gamma }^{\mathrm{1,1}}$, P is 2-convex if and only if there exists an L-path from

1) $\{\begin{array}{c}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\mathrm{<mi>\; </mi>}\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (S)\end{array}$

or

2) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\mathrm{<mi>\; </mi>}\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (E)\end{array}$

or

3) $\{\begin{array}{c}\max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ \max \left(W\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

4) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

Corollary 1. If P satisfies the conditions of Theorem 2, then P is in the class ${\gamma }_{2L}^{\mathrm{1,1}}$ and hence it is in the class ${\alpha }_{2L}^{\mathrm{1,1}}$ (see Figure 7).

Theorem 2. Let P be a convex polyomino in the class ${\delta }^{\mathrm{1,1}}$, P is 2-convex if and only if there exists an L-path from

1) $\{\begin{array}{c}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (S)\end{array}$

or

2) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

3) $\{\begin{array}{c}\max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ \max \left(W\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

4) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (E)\end{array}$

or

5) $\{\begin{array}{c}\max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ \text{the corner cell in}WN\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ 2L\text{-path starting by a south step from}\mathrm{<mi>\; </mi>}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

6) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by a south step from}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max (S)\end{array}$

or

7) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ 2L\text{-path starting by a south step fromthe corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

Corollary 2. If P satisfies the conditions of Theorem 3, then P is in the class ${\delta }_{2L}^{\mathrm{1,1}}$ and hence it is in the class ${\alpha }_{2L}^{\mathrm{1,1}}$ (see Figure 8).

Theorem 3. Let P be a convex polyomino in the class ${\Delta }^{\mathrm{1,1}}$, P is 2-convex if and only if there exists an L-path from

1) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (E)\end{array}$

or

2) $\{\begin{array}{c}\max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ \max \left(W\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

3) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

4) $\{\begin{array}{c}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ \text{the corner cell in}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (S)\end{array}$

or

5) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ 2L\text{-path starting by an east step from}\mathrm{<mi>\; </mi>}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

6) $\{\begin{array}{c}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ \mathrm{<mi>\; </mi>}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by an east step from}\\ \mathrm{<mi>\; </mi>}\text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max (E)\end{array}$

or

7) $\{\begin{array}{c}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ \max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ 2L\text{-path starting by an east step fromthe corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

Corollary 3. If P satisfies the conditions of Theorem 4, then P is in the class ${\Delta }_{2L}^{\mathrm{1,1}}$ and hence it is in the class ${\alpha }_{2L}^{\mathrm{1,1}}$ (see Figure 9).

Theorem 4. Let P be a convex polyomino in the class ${\chi }^{\mathrm{1,1}}$, P is 2-convex if and only if there exists an L-path from

1) $\{\begin{array}{c}\max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ \max \left(W\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

2) $\{\begin{array}{c}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ \min \left(W\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by an east step from}\mathrm{<mi>\; </mi>}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max (E)\end{array}$

or

3) $\{\begin{array}{c}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (S)\end{array}$

or

4) $\{\begin{array}{c}\max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ 2L\text{-path starting by a south step from}\mathrm{<mi>\; </mi>}\mathrm{mi}(\left(N\right)\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

5) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

6) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by a south step from}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max (S)\end{array}$

or

7) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min (E)\end{array}$

or

8) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ 2L\text{-path starting by an east step from}\mathrm{<mi>\; </mi>}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

9) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ 2L\text{-path starting by an east step from}\\ \text{the corner cell in}WN\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

10) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ 2L\text{-path starting by an east step fromthe corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by a south step from}\mathrm{<mi>\; </mi>}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

11) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ and\\ \min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ 2L\text{-path starting by an east step fromto}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by a south step from}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max (S)\end{array}$

or

12) $\{\begin{array}{c}\max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ \min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ 2L\text{-path starting by a south step from}\mathrm{<mi>\; </mi>}\\ \text{the corner cell in}WN\text{tothe corner cell in}SE\end{array}$

or

13) $\{\begin{array}{c}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(E\right)\\ \text{and}\\ 2L\text{-path starting by a south step from}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by an east step from}\mathrm{<mi>\; </mi>}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

14) $\{\begin{array}{c}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(S\right)\\ \text{and}\\ \min \left(N\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ 2L\text{-path starting by a south step from}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{tothe corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by an east step from}\\ \text{the corner cell in}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max (E)\end{array}$

Corollary 4. If P satisfies the conditions of Theorem 5, then P is in the class ${\chi }_{2L}^{\mathrm{1,1}}$ and hence it is in the class ${\alpha }_{2L}^{\mathrm{1,1}}$ (see Figure 10 and Figure 11).

4. HV-Convex Polyominoes

Assume that H, V denote strictly positive row and column sum vectors. We also assume that ${\displaystyle {\sum }_i{h}_i}={\displaystyle {\sum }_j{v}_j}$, since otherwise $\left(H\mathrm{,}V\right)$ do not have a realization.

The idea of Chrobak and Dürr [8] for reconstructing an HV-convex polyomino is to impose convexity on the four corner regions outside of the polyomino.

An object A is called an upper-left corner region if $\left(i+\mathrm{1,}j\right)\in A$ or $\left(i\mathrm{,}j+1\right)\in A$ implies $\left(i\mathrm{,}j\right)\in A$. In an analogous way other corner regions can be defined. Let $\bar{P}$ be the complement of P. The definition of HV-convex polyominoes directly implies the following lemma.

Lemma 1. P is an HV-convex polyomino if and only if $\bar{P}=A\cup B\cup C\cup D$, where $A\mathrm{,}B\mathrm{,}C\mathrm{,}D$ are disjoint corner regions (upper-left, upper-right, lower-left and lower-right, respectively) such that 1) $\left(i-\mathrm{1,}j-1\right)\in A$ implies $\left(i\mathrm{,}j\right)$ not in D, and 2) $\left(i-\mathrm{1,}j+1\right)\in B$ implies $\left(i\mathrm{,}j\right)\notin C$.

Given an HV-convex polyomino P and two row indices $1\le k\mathrm{,}l\le m$. P is anchored at $\left(k\mathrm{,}l\right)$ if $\left(k\mathrm{,1}\right)\mathrm{,}\left(l\mathrm{,}n\right)\in P$. The idea of Chrobak and Dürr is, given $\left(H\mathrm{,}V\right)$, to reconstruct a 2SAT expression (a boolean expression in conjunctive normal form with at most two literals in each clause) $F_{k\mathrm{,}l}\left(H\mathrm{,}V\right)$ with the property that $F_{k\mathrm{,}l}\left(H\mathrm{,}V\right)$ is satisfiable iff there is an HV-convex polyomino realization P of $\left(H\mathrm{,}V\right)$ that is anchored at $\left(k\mathrm{,}l\right)$. $F_{k\mathrm{,}l}\left(H\mathrm{,}V\right)$ consists of several sets of clauses, each set expressing a certain property: “Corners” (Cor), “Disjointness” (Dis), “Connectivity” (Con), “Anchors” (Anc), “Lower bound on column sums” (LBC) and “Upper bound on row sums” (UBR).

$Cor={{\displaystyle \wedge }}_{i\mathrm{,}j}\left\{\begin{array}{cccc}{A}_{i\mathrm{,}j}\Rightarrow A_{i-\mathrm{1,}j}& B_{i\mathrm{,}j}\Rightarrow B_{i-\mathrm{1,}j}& C_{i\mathrm{,}j}\Rightarrow C_{i+\mathrm{1,}j}& D_{i\mathrm{,}j}\Rightarrow D_{i+\mathrm{1,}j}\\ A_{i\mathrm{,}j}\Rightarrow A_{i\mathrm{,}j-1}& B_{i\mathrm{,}j}\Rightarrow B_{i\mathrm{,}j+1}& C_{i\mathrm{,}j}\Rightarrow C_{i\mathrm{,}j-1}& D_{i\mathrm{,}j}\Rightarrow D_{i\mathrm{,}j+1}\end{array}\right\}$

The set of clauses $Cor$ means that the corners are convex, that is for the corner A if the cell $\left(i\mathrm{,}j\right)$ belongs to A then cells $\left(i-\mathrm{1,}j\right)$ and $\left(i\mathrm{,}j-1\right)$ belong also to A. Similarly for corners B, C, and D.

$Dis={{\displaystyle \wedge }}_{i\mathrm{,}j}\left\{X_{i\mathrm{,}j}\Rightarrow {\bar{Y}}_{i\mathrm{,}j}\mathrm{<mo>\; :\; </mo>\; <mi>\; </mi>}\text{forsymbols}\mathrm{<mi>\; </mi>}X\mathrm{,}Y\in \left\{A\mathrm{,}B\mathrm{,}C\mathrm{,}D\right\}\mathrm{,}X\ne Y\right\}$

The set of clauses $Dis$ means that all four corners are pairwise disjoint, that is $X\cap Y=\varnothing$ for $X\mathrm{,}Y\in \left\{A\mathrm{,}B\mathrm{,}C\mathrm{,}D\right\}$.

$Con={{\displaystyle \wedge }}_{i\mathrm{,}j}\left\{\begin{array}{cc}{A}_{i\mathrm{,}j}\Rightarrow {\bar{D}}_{i+\mathrm{1,}j+1}& B_{i\mathrm{,}j}\Rightarrow {\bar{C}}_{i+\mathrm{1,}j-1}\end{array}\right\}$

The set of clauses $Con$ means that if the cell $\left(i\mathrm{,}j\right)$ belongs to A then the cell $\left(i+\mathrm{1,}j+1\right)$ does not belong to D, and similarly if the cell $\left(i\mathrm{,}j\right)$ belongs to B then the cell $\left(i+\mathrm{1,}j-1\right)$ does not belong to C.

$Anc=\left\{{\bar{A}}_{k\mathrm{,1}}\wedge {\bar{B}}_{k\mathrm{,1}}\wedge {\bar{C}}_{k\mathrm{,1}}\wedge {\bar{D}}_{k\mathrm{,1}}\wedge {\bar{A}}_{l\mathrm{,}n}\wedge {\bar{B}}_{l\mathrm{,}n}\wedge {\bar{C}}_{l\mathrm{,}n}\wedge {\bar{D}}_{l\mathrm{,}n}\right\}$

The set of clauses $Anc$ means that we fix two cells on the west and east feet of the polyomino P, for $k,l=1,\cdots ,m$ the first one at the position $\left(k\mathrm{,1}\right)$ and the second one at the position $\left(l\mathrm{,}n\right)$.

$LBC={{\displaystyle \wedge }}_{i\mathrm{,}j}\left\{\begin{array}{cc}{A}_{i\mathrm{,}j}\Rightarrow {\bar{C}}_{i+v_j\mathrm{,}j}& A_{i\mathrm{,}j}\Rightarrow {\bar{D}}_{i+v_j\mathrm{,}j}\\ B_{i\mathrm{,}j}\Rightarrow {\bar{C}}_{i+v_j\mathrm{,}j}& B_{i\mathrm{,}j}\Rightarrow {\bar{D}}_{i+v_j\mathrm{,}j}\end{array}\right\}\wedge {{\displaystyle \wedge }}_j\left\{\begin{array}{cc}{\bar{C}}_{v_j\mathrm{,}j}& {\bar{D}}_{v_j\mathrm{,}j}\end{array}\right\}$

The set of clauses LBC implies that for each column j, we have that ${\displaystyle {\sum }_i{P}_{i\mathrm{,}j}}\ge v_j$.

$UBR={{\displaystyle \wedge }}_j\left\{\begin{array}{cc}{\wedge }_{i\le \min \left\{k,l\right\}}{\bar{A}}_{i\mathrm{,}j}\Rightarrow B_{i\mathrm{,}j+h_i}& {\wedge }_{k\le i\le l}{\bar{C}}_{i\mathrm{,}j}\Rightarrow B_{i\mathrm{,}j+h_i}\\ {\wedge }_{l\le i\le k}{\bar{A}}_{i\mathrm{,}j}\Rightarrow D_{i\mathrm{,}j+h_i}& {\wedge }_{\max \left\{k,l\right\}\le i}{\bar{C}}_{i\mathrm{,}j}\Rightarrow D_{i\mathrm{,}j+h_i}\end{array}\right\}$

The set of clauses UBR implies that for each row i, we have that ${\displaystyle {\sum }_j{P}_{i\mathrm{,}j}}\le h_i$.

Define $F_{k\mathrm{,}l}\left(H\mathrm{,}V\right)=Cor\wedge Dis\wedge Con\wedge Anc\wedge LBC\wedge UBR$. All literals with indices outside the set $\left\{\mathrm{1,}\cdots \mathrm{,}m\right\}\times \left\{\mathrm{1,}\cdots \mathrm{,}n\right\}$ are assumed to have value 1.

The following theorem allows to link the existence of HV-convex solution and the evaluation of $F_{k\mathrm{,}l}\left(H\mathrm{,}V\right)$. The crucial part of this algorithm comes from the constraints on the two sets of clauses LBC and UBR.

Theorem 5 (Chrobak, Durr). $F_{k\mathrm{,}l}\left(H\mathrm{,}V\right)$ is satisfiable if and only if $\left(H\mathrm{,}V\right)$ have a realization P that is an HV-convex polyomino anchored at $\left(k\mathrm{,}l\right)$.

Each formula $F_{k\mathrm{,}l}\left(H\mathrm{,}V\right)$ has size $O\left(mn\right)$ and can be computed in time $O\left(mn\right)$. Since 2SAT can be solved in linear time see [11] [12] , Chrobak and Dürr give the following result.

Theorem 6 (Chrobak, Durr). Algorithm 1 solves the reconstruction problem for HV-convex polyominoes in time $O\left(mn\min \left(m^2,n^2\right)\right)$.

5. Reconstruction of 2-Convex Polyominoes in ${\alpha }_{2L}^{1,1}$

The present section uses the theoretical material of the previous sections in order to reconstruct 2-convex polyominoes in the class ${\alpha }_{2L}^{\mathrm{1,1}}$. Some modifications are made to the reconstruction algorithm of Chrobak and Dürr for HV-convex polyominoes in order to impose our geometries.

Finally, by defining an horizontal symmetry $S_H$, we show how to reconstruct P in the class ${\beta }_{2L}^{\mathrm{1,1}}$.

5.1. Clauses for the Class ${\gamma }_{2L}^{1,1}$

We code by a 2SAT formula the four geometries that characterize all 2-convex polyominoes in the class ${\gamma }_{2L}^{\mathrm{1,1}}$ in order to reconstruct them.

$Pos=\left\{\begin{array}{c}{C}_{\left(\max \left(W\right)+\mathrm{1,1}\right)}\wedge C_{\left(m\mathrm{,}\max \left(N\right)\right)}\wedge A_{\mathrm{1,1}}\wedge D_{m\mathrm{,}n}\end{array}\right\}$

$Cor={{\displaystyle \wedge }}_{i\mathrm{,}j}\left\{\begin{array}{cccc}{A}_{i\mathrm{,}j}\Rightarrow A_{i-\mathrm{1,}j}& B_{i\mathrm{,}j}\Rightarrow B_{i-\mathrm{1,}j}& C_{i\mathrm{,}j}\Rightarrow C_{i+\mathrm{1,}j}& D_{i\mathrm{,}j}\Rightarrow D_{i+\mathrm{1,}j}\\ A_{i\mathrm{,}j}\Rightarrow A_{i\mathrm{,}j-1}& B_{i\mathrm{,}j}\Rightarrow B_{i\mathrm{,}j+1}& C_{i\mathrm{,}j}\Rightarrow C_{i\mathrm{,}j-1}& D_{i\mathrm{,}j}\Rightarrow D_{i\mathrm{,}j+1}\end{array}\right\}$

$Dis={{\displaystyle \wedge }}_{i\mathrm{,}j}\left\{X_{i\mathrm{,}j}\Rightarrow {\bar{Y}}_{i\mathrm{,}j}\mathrm{<mo>\; :\; </mo>\; <mi>\; </mi>}\text{forsymbols}\mathrm{<mi>\; </mi>}X\mathrm{,}Y\in \left\{A\mathrm{,}B\mathrm{,}C\mathrm{,}D\right\}\mathrm{,}X\ne Y\right\}$

$Con={{\displaystyle \wedge }}_{i\mathrm{,}j}\left\{\begin{array}{cc}{A}_{i\mathrm{,}j}\Rightarrow {\bar{D}}_{i+\mathrm{1,}j+1}& B_{i\mathrm{,}j}\Rightarrow {\bar{C}}_{i+\mathrm{1,}j-1}\end{array}\right\}$

$Anc=\left\{\begin{array}{c}{\bar{A}}_{\min \left(W\right),1}\wedge {\bar{A}}_{\max \left(W\right)+1,n}\wedge {\bar{B}}_{\min \left(W\right),1}\wedge {\bar{B}}_{\max \left(W\right)+1,n}\wedge \\ {\bar{C}}_{\min \left(W\right),1}\wedge {\bar{C}}_{\max \left(W\right)+1,n}\wedge {\bar{D}}_{\min \left(W\right),1}\wedge {\bar{D}}_{\max \left(W\right)+1,n}\wedge \\ {\bar{A}}_{1,\min \left(N\right)}\wedge {\bar{A}}_{m,\max \left(N\right)+1}\wedge {\bar{B}}_{1,\min (N)}\wedge {\bar{B}}_{m,\max \left(N\right)+1}\wedge \\ {\bar{C}}_{1,\min \left(N\right)}\wedge {\bar{C}}_{m,\max \left(N\right)+1}\wedge {\bar{D}}_{1,\min (N)}\wedge {\bar{D}}_{m,\max \left(N\right)+1}\wedge \\ {\bar{A}}_{\max \left(W\right),1}\wedge {\bar{A}}_{\max \left(E\right),n}\wedge {\bar{B}}_{\max \left(W\right),1}\wedge {\bar{B}}_{\max \left(E\right),n}\wedge \\ {\bar{C}}_{\max \left(W\right),1}\wedge {\bar{C}}_{\max \left(E\right),n}\wedge {\bar{D}}_{\max \left(W\right),1}\wedge {\bar{D}}_{\max \left(E\right),n}\wedge \\ {\bar{A}}_{1,\max \left(N\right)}\wedge {\bar{A}}_{m,\max \left(S\right)}\wedge {\bar{B}}_{1,\max \left(N\right)}\wedge {\bar{B}}_{m,\max \left(S\right)}\wedge \\ {\bar{C}}_{1,\max \left(N\right)}\wedge {\bar{C}}_{m,\max \left(S\right)}\wedge {\bar{D}}_{1,\max \left(N\right)}\wedge {\bar{D}}_{m,\max \left(S\right)}\end{array}\right\}$

$\begin{array}{l}LBC={{\displaystyle \wedge }}_i\left\{\begin{array}{cc}{\wedge }_{j<\min \left(N\right)}{A}_{i,j}\Rightarrow {\bar{C}}_{i+v_j,j}& {\wedge }_{\max \left(N\right)+1\le j\le \max \left(S\right)}{B}_{i,j}\Rightarrow {\bar{C}}_{i+v_j,j}\\ {\wedge }_{\min \left(N\right)\le j\le \max \left(N\right)}{C}_{i+v_j,j}\Rightarrow {\bar{A}}_{i,j}& {\wedge }_{j>\max \left(S\right)}{B}_{i,j}\Rightarrow {\bar{D}}_{i+v_j,j}\\ {\wedge }_{\max \left(N\right)<j<\max \left(N\right)+1}{B}_{i,j}\Rightarrow {\bar{C}}_{i+v_j,j}& \end{array}\right\}\\ \wedge {{\displaystyle \wedge }}_j\left\{\begin{array}{cc}{\bar{C}}_{v_j\mathrm{,}j}& {\bar{D}}_{v_j\mathrm{,}j}\end{array}\right\}\end{array}$

$UBR={{\displaystyle \wedge }}_j\left\{\begin{array}{cc}{\wedge }_{i<\max \left(W\right)+1}{\bar{A}}_{i,j}\Rightarrow B_{i,j+h_i}& {\wedge }_{\min \left(W\right)\le i\le \max \left(W\right)}{\bar{A}}_{i,j}\Rightarrow D_{i,j+h_i}\\ {\wedge }_{\max \left(W\right)+1\le i\le \max \left(E\right)}{\bar{B}}_{i,j+h_i}\Rightarrow A_{i,j}& {\wedge }_{i>\max \left(W\right)}{\bar{C}}_{i,j}\Rightarrow D_{i,j+h_i}\\ {\wedge }_{\max \left(E\right)<i<\min \left(W\right)}{\bar{A}}_{i,j}\Rightarrow D_{i,j+h_i}& \end{array}\right\}$

$REC=\left\{\begin{array}{c}{\bar{A}}_{\min \left(W\right)-\mathrm{1,}\min \left(N\right)-1}\wedge {\bar{D}}_{\max \left(E\right)+\mathrm{1,}\max \left(S\right)+1}\end{array}\right\}$

$REC1=\left\{\begin{array}{c}{A}_{\min \left(W\right)-\mathrm{1,}\min \left(N\right)-2}\wedge A_{\min \left(W\right)-\mathrm{2,}\min \left(N\right)-1}\wedge D_{\max \left(E\right)+\mathrm{1,}\max \left(S\right)+2}\\ \wedge D_{\max \left(E\right)+\mathrm{2,}\max \left(S\right)+1}\end{array}\right\}$

$GEO1=\left\{\begin{array}{c}{\bar{A}}_{\min \left(N\right),\max \left(W\right)+1}\wedge {\bar{B}}_{\min \left(N\right),\max \left(W\right)+1}\wedge {\bar{C}}_{\min \left(N\right),\max \left(W\right)+1}\\ \wedge {\bar{D}}_{\min \left(N\right),\max \left(W\right)+1}\wedge {\bar{A}}_{\min \left(W\right)-1,\max \left(N\right)+1}\wedge {\bar{B}}_{\min \left(W\right)-1,\max \left(N\right)+1}\\ \wedge {\bar{C}}_{\min \left(W\right)-1,\max \left(N\right)+1}\wedge {\bar{D}}_{\min \left(W\right)-1,\max \left(N\right)+1}\end{array}\right\}$

$GEO2=\left\{\begin{array}{c}{\bar{A}}_{\min \left(W\right),\max \left(N\right)+1}\wedge {\bar{B}}_{\min \left(W\right),\max \left(N\right)+1}\wedge {\bar{C}}_{\min \left(W\right),\max \left(N\right)+1}\\ \wedge {\bar{D}}_{\min \left(W\right),\max \left(N\right)+1}\wedge {\bar{A}}_{\min \left(W\right)-1,\max \left(W\right)+1}\wedge {\bar{B}}_{\min \left(W\right)-1,\max \left(W\right)+1}\\ \wedge {\bar{C}}_{\min \left(W\right)-1,\max \left(W\right)+1}\wedge {\bar{D}}_{\min \left(W\right)-1,\max \left(W\right)+1}\end{array}\right\}$

$GEO3=\left\{\begin{array}{c}{\bar{A}}_{\max \left(E\right),\max \left(N\right)}\wedge {\bar{B}}_{\max \left(E\right),\max \left(N\right)}\wedge {\bar{C}}_{\max \left(E\right),\max \left(N\right)}\\ \wedge {\bar{D}}_{\max \left(E\right),\max \left(N\right)}\wedge {\bar{A}}_{\max \left(W\right),\max \left(S\right)+1}\wedge {\bar{B}}_{\max \left(W\right),\max \left(S\right)+1}\\ \wedge {\bar{C}}_{\max \left(W\right),\max \left(S\right)+1}\wedge {\bar{D}}_{\max \left(W\right),\max \left(S\right)+1}\end{array}\right\}$

$GEO4=\left\{\begin{array}{c}{\bar{A}}_{\max \left(W\right),\max \left(S\right)}\wedge {\bar{B}}_{\max \left(W\right),\max \left(S\right)}\wedge {\bar{C}}_{\max \left(W\right),\max \left(S\right)}\\ \wedge {\bar{D}}_{\max \left(W\right),\max \left(S\right)}\wedge {\bar{A}}_{\max \left(E\right)+1,\max \left(N\right)}\wedge {\bar{B}}_{\max \left(E\right)+1,\max \left(N\right)}\\ \wedge {\bar{C}}_{\max \left(E\right)+1,\max \left(N\right)}\wedge {\bar{D}}_{\max \left(E\right)+1,\max \left(N\right)}\end{array}\right\}$

In order to reconstruct all 2-convex polyominoes in the class ${\gamma }_{2L}^{\mathrm{1,1}}$, we use the set of clauses that impose the 4 geometries.

$\begin{array}{l}{\gamma }_{2L\mathrm{,}Geo1}^{\mathrm{1,1}}\left(H\mathrm{,}V\right)=Pos\wedge Cor\wedge Dis\wedge Con\wedge Anc\wedge LBC\wedge UBR\\ \wedge REC\wedge REC1\wedge GEO1.\end{array}$