ABSTRACT

A polyomino P is called 2-convex if for every two cells there exists a monotone path included in P with at most two changes of direction. This paper studies the geometrical properties of a sub-class of 2-convex polyominoes called ${\alpha }_{2L}^{\mathrm{1,1}}$ where the upper left corner and the lower right corner of the polyomino each contains only one cell.

Keywords:

Polyomino, Convex Objects, Monotone Path

1. Introduction

Discrete convexity intervenes in many domains with regard to geometry and particularly to image processing.

Many notions of discrete convexity of polyominoes were investigated (see [1] , [2] and [3] ). One natural notion is the class of HV-convex polyominoes, where polyominoes have consecutive cells in columns and rows. Also HV-convex polyominoes possess the property that every pair of cells can be connected using a montone path included included in the polyominoes and having only two ypes of unit steps (see [4] [5] ).

An HV-convex polymino is called k-convex if for every two cells one can find a monotone path with at most k changes of direction. When the value of k is equal to 1, we have the class of 1-convex polyominoes. This notion of 1-convex polyominoes has been investigated by different researchers (see [3] [6] [7] ). In fact, 2-convex polymoninoes are geometrically more complicated than the 1-convex polyominoes and should be divided into different sublclasses in order to study them(see [4] [5] ).

In [4] , it has been showed that if P is an HV-centered polyomino then P is 2-convex. The reconstruction algorithm of HV-centered polyomino is available in [8] .

From now on, 2-convex polyominoes which are not L-convex and HV-centered are considered.

In [4] it has been showed that if P is an HV-convex polyomino, and if the N-foot is situated to the left (resp. to the right) of the S-foot and the E-foot is situated to the north (resp. to the south) of the W-foot then P is a 2-convex polyomino. The tomographical aspects of this is available in [5] [8] .

Another subclass of 2-convex polyominoes has been studied in [4] where the N-foot is situated to the left (resp. to the right) of the S-foot and the E-foot is situated to the south (resp. to the north) of the W-foot. This subclass possesses the property that the upper left corner and the lower right corner are empty of cells. The geometrical and tomographical properties of this subclass are available in [5] ).

Directed 2-convex polyominoes with empty corners have been studied in [4] , their tomographical aspects are not similar to the other subclasses but their direct reconstruction is always possible.

In this paper, the study of the 2-convex polyominoes subclasses continues by investigating the geometrical properties of another subclass called ${\alpha }_{2L}^{\mathrm{1,1}}$ where the lower right corner and the upper left corner are non-empty and each contains only one cell.

This paper is divided into 4 sections. In the first section, an introduction on the different works done before on convex, 1-convex, and some sublcasses of 2-convex polyominoes is given. In the second section, different notations on the feet of the polyominoes are introduced in order to understand the geometrical shapes of the class ${\alpha }_{2L}^{\mathrm{1,1}}$ . In the third section, 32 geometries in the class ${\alpha }_{2L}^{\mathrm{1,1}}$ are given. The last section is reserved for the future work.

2. Definitions and Notations

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 plane geometric figure formed by joining one or more equal squares edge to edge. 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 HV-convex if it is both row and column-convex (see [4] ) (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 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 $\left(i\mathrm{,}j\right)$ denotes the entry in row i and column j.

For any two cells $A=\left(i_1,j_1\right)$ and $B=\left(i_r,j_r\right)$ in a polyomino P, a path from A to B, is a sequence of adjacent disjoint cells belonging to P. 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$ .

Definition 1. A path in a polyomino P is said to be monotone if it is entirely made of the four types of steps defined above (see [4] [5] ).

Proposition 1 (Castiglione, Restivo [7] ). 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 2. An HV-convex polyomino is said to be k-convex if every pair of its cells can be connected by a monotone path with at most k changes of direction respectively.

In the present study, we focus our attention on 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. Geometrical Aspects

In this section, we study the geometrical aspects of 2-convex polyominoes in terms of positions of the feet. Let $\left(H\mathrm{,}V\right)$ be two vectors of projections, and let P be a convex polyomino that satisfies $\left(H\mathrm{,}V\right)$ . By a classical argument, P is contained in a rectangle R of size $m\times n$ (called minimal bounding box). Let $\left[\min \left(S\right)\mathrm{,}\max \left(S\right)\right]$ ( $\left[\min \left(E\right)\mathrm{,}\max \left(E\right)\right]$ , $\left[\min \left(N\right)\mathrm{,}\max \left(N\right)\right]$ , $\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, for each $1\le i\le m$ and $1\le j\le n$ , 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) (see [4]).

Definition 3. 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 (see [4] ).

Definition 4. Let P be an HV-convex polyomino, we say that P is h-centered [resp. v-centered], if its W-foot and E-foot [resp. N-foot and S-foot] intersect, that is there at least one row going from one foot to another (see Figure 6), (see [8] ).

The following property links h-centered polyominoes or v-centered polyominoes to 2-convex polyominoes :

Proposition 2. If P is an h-centered polyomino or a v-centered polyomino, then it is a 2-convex polyomino (see [4] ).

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

• $\alpha =\left\{P\in \mathcal{C}\mathrm{<mi>\; </mi>\; <mo>\; |\; </mo>\; <mi>\; </mi>}\max \left(N\right)<\min \left(S\right)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\max \left(W\right)<\min \left(E\right)\right\}$

• $\beta =\left\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\max \left(S\right)<\min \left(N\right)\text{and}\mathrm{<mi>\; </mi>}\max \left(E\right)<\min \left(W\right)\right\}$ .

Let us define the horizontal transformation (symmetry) [4] $S_H\mathrm{<mo>\; :\; </mo>}\left(i\mathrm{,}j\right)\to \left(m-i+\mathrm{1,}j\right)$ which transforms the polyomino P from the class $\alpha$ to the class $\beta$ (see Figure 7).

The study of the classes $\alpha$ and $\beta$ is very complicated until now. So we make the choice of studying one special case called ${\alpha }^{\mathrm{1,1}}$ where the lower right corner and the upper left corner of the polyomino contain each only one cell (see Figure 8). For this case, we study the geometrical properties in order to

describe the geometries of 2-convex polyominoes in the class ${\alpha }^{\mathrm{1,1}}$ and to give characterizations of such 2-convex polyominoes in terms of paths.

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

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

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

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

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

The above sets with the classes $\alpha$ and $\beta$ allow us to define the following two classes:

• $\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}$ , (see Figure 8)

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

• $\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)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=1\text{and}\mathrm{<mi>\; </mi>}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)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\max \left(E\right)<\min \left(W\right);\\ card\left(NE\right)=\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}card\left(WS\right)=1\}\end{array}$ , where P is a 2-convex polyomino.

Note that the horizontal symmetry $S_H$ maps ${\alpha }_{2L}^{\mathrm{1,1}}$ to ${\beta }_{2L}^{\mathrm{1,1}}$ .

The following characterization holds for convex polyominoes in the class ${\alpha }^{\mathrm{1,1}}$ .

Theorem 1. Let P be a convex polyomino in the class ${\alpha }^{\mathrm{1,1}}$ , P is 2-convex if and only if there exist nine paths:

1) from $\min \left(N\right)$ to $\max \left(E\right)$ ,

2) and from $\min \left(N\right)$ to $\max \left(S\right)$ ,

3) and from $\min \left(W\right)$ to $\max \left(E\right)$ ,

4) and from $\min \left(W\right)$ to $\max \left(S\right)$ ,

5) and from the corner cell in WN to $\max \left(E\right)$ ,

6) and from the corner cell in WN to $\max \left(S\right)$ ,

7) and from $\min \left(N\right)$ to the corner cell in SE,

8) and from $\min \left(W\right)$ to the corner cell in SE,

9) and from the corner cell in WN to the corner cell in SE, having at most two changes of direction.

Proof. (Þ) It is an immediate consequence of the definition of 2-convex polyominoes.

(Ü) Suppose that P is not 2-convex, then there exist two cells $\left(i\mathrm{,}j\right)$ and $\left(i^{\prime }\mathrm{,}{j}^{\prime }\right)$ such that any path between them has more than two changes of direction. Let us suppose that $\left(i\mathrm{,}j\right)$ is at the position $\left(\min \left(W\right)\le i\le \max \left(W\right)\mathrm{,1}\right)$ and $\left(i^{\prime }\mathrm{,}{j}^{\prime }\right)$ is at the position $\left(m\mathrm{,}\min \left(S\right)\le j^{\prime }\le \max \left(S\right)\right)$ (the other positions are similar). We have the following cases.

CASE 1:

If the path from $\min \left(W\right)$ to the corner cell in SE has one change of direction, i.e. there exists an L-path between them, then by convexity there is an L-path between $\left(i\mathrm{,}j\right)$ and $\left(i^{\prime }\mathrm{,}{j}^{\prime }\right)$ , hence the contradiction.

CASE 2:

If the path from $\min \left(W\right)$ to the corner cell in SE has two changes of direction, one can observe the following cases.

• Either the path goes through $\min \left(S\right)$ and then there exist an L-path between $\min \left(W\right)$ and $\min \left(S\right)$ , thus by convexity there exists a 2L-path from $\left(i\mathrm{,}j\right)$ to $\left(i^{\prime }\mathrm{,}{j}^{\prime }\right)$ , hence the contradiction; or

• The path goes through $\max \left(W\right)$ and then there is an L-path between $\max \left(W\right)$ and the corner cell in SE, thus there exists a 2L-path from $\left(i\mathrm{,}j\right)$ to $\left(i^{\prime }\mathrm{,}{j}^{\prime }\right)$ , hence the contradiction; or

• The path goes through $\max \left(N\right)$ and then there is an L-path between $\max \left(N\right)$ and the corner cell in SE, thus there exists a 2L-path from $\left(i\mathrm{,}j\right)$ to $\left(i^{\prime }\mathrm{,}{j}^{\prime }\right)$ , hence the contradiction; or

• The path goes through a path where its vertical position is between $\max \left(N\right)$ and $\min \left(S\right)$ , thus there exists a 2L-path from $\left(i\mathrm{,}j\right)$ to $\left(i^{\prime }\mathrm{,}{j}^{\prime }\right)$ , hence the contradiction (see Figure 9).

The cases (1), (2), (3), (4), (5), (6), (7) are similar up to symmetry. $\square$

Corollary 1. If P satisfies Theorem 1, then P is in the class ${\alpha }_{2L}^{\mathrm{1,1}}$ (see Figure 10).

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)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}card\left(SE\right)=1;\\ \min \left(E\right)=\max \left(w\right)+\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\min \left(S\right)=\max \left(N\right)+1\}\end{array}$ (see Figure 11).

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

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

• $\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}\mathrm{<mi>\; </mi>}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}card\left(SE\right)=1;\\ \min \left(E\right)\ne \max \left(w\right)+\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\min \left(S\right)\ne \max \left(N\right)+1\}\end{array}$ (see Figure 11).

• $\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}\mathrm{<mi>\; </mi>}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}card\left(SE\right)=1;\\ \min \left(E\right)=\max \left(w\right)+\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\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)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\max \left(E\right)<\min \left(W\right);\\ card\left(NE\right)=\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}card\left(WS\right)=1;\\ \min \left(E\right)\ne \max \left(W\right)+\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\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)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}card\left(SE\right)=1;\\ \min \left(E\right)=\max \left(w\right)+\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\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)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\max \left(W\right)<\min \left(E\right);\\ card\left(WN\right)=\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}card\left(SE\right)=1;\\ \min \left(E\right)\ne \max \left(w\right)+\mathrm{1\; <mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}\min \left(S\right)\ne \max \left(N\right)+1\}\end{array}$ , where P is a 2-convex polyomino.

Theorem 2. 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\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{to the 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{to the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

Proof. (Ü) Suppose that P satisfies only the first geometry, i.e. there exist L-paths from $\min \left(N\right)$ to $\min \left(E\right)$ and from the corner cell in WN to $\min \left(S\right)$ . From the first L-path, one can deduce that there exist 2L-paths from $\min \left(N\right)$ to $\max \left(E\right)$ , from $\min \left(N\right)$ to $\max \left(E\right)$ and from $\min \left(N\right)$ to the corner cell in SE. Now from the second L-path, one can deduce that there exist 2L-paths from $\min \left(W\right)$ to $\max \left(S\right)$ , from $\min \left(W\right)$ to $\max \left(E\right)$ , from $\min \left(W\right)$ to the corner cell in SE, from the corner cell in WN to $\max \left(E\right)$ , from the corner cell in WN to $\max \left(S\right)$ , and finally from the corner cell in WN to the corner cell in SE. To summarize, all nine paths in Theorem 1 are in P and hence P is 2-convex.

Similar reasoning holds for the geometries (2), (3), and (4).

(Þ) P is 2L-convex polyomino then, there exist 2L-paths from $\min \left(W\right)$ to $\max \left(E\right)$ , from $\min \left(N\right)$ to $\max \left(S\right)$ , from $\min \left(N\right)$ to the corner cell in SE, from $\min \left(W\right)$ to the corner cell in SE, from the corner cell in WN to $\max \left(E\right)$ , and from the corner cell in WN to $\max \left(S\right)$ . Now, suppose that the four minimal geometries in Figure 12 are not satisfied. Then we have the following possibilities.

1) There exist L-paths from $\min \left(N\right)$ to the corner cell in SE and from $\max \left(W\right)$ to $\min \left(S\right)$ . From the first L-path, one can deduce that there exists an L-path between $\max \left(N\right)$ and the corner cell in SE. From the second L-path, one can see that there is no information between $\min \left(W\right)$ and $\max \left(S\right)$ , hence P is not 2L-convex polyomino.

2) There exist L-paths from the corner cell in WN to $\max \left(S\right)$ and from $\max \left(N\right)$ to $\min \left(E\right)$ . From the first L-path, one can deduce that there is an L-path between the corner cell in WN to $\min \left(S\right)$ . From the second L-path, one can see that there is no information between $\min \left(N\right)$ and $\max \left(E\right)$ , hence P is not 2L-convex polyomino.

3) There exist L-paths from $\min \left(W\right)$ to the corner cell in SE and from $\max \left(N\right)$ to $\min \left(E\right)$ . From the first L-path, one can deduce that there exists an L-path between $\max \left(N\right)$ and the corner cell in SE. From the second L-path, one can see that there is no information between $\min \left(N\right)$ and $\max \left(E\right)$ , hence P is not 2L-convex polyomino.

4) There exist L-paths from the corner cell in WN to $\max \left(E\right)$ and from $\max \left(W\right)$ to $\min \left(S\right)$ . From the first L-path, one can deduce that there is an L-path between the corner cell in WN to $\min \left(S\right)$ . From the second L-path, one can see that there is no information between $\min \left(W\right)$ and $\max \left(E\right)$ , hence P is not 2L-convex polyomino.

In conclusion, the four geometries are necessary to characterize a 2L-convex polyomino in the class ${\gamma }^{\mathrm{1,1}}$ (see Figure 12).

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

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(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}\max \left(W\right)\mathrm{<mi>\; </mi>}\text{to}\mathrm{<mi>\; </mi>}\max \left(S\right)\mathrm{<mi>\; </mi>}\\ \text{and}\\ \max \left(N\right)\mathrm{<mi>\; </mi>}\text{to the 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{to the 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}\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>}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to 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{to the corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by asouth step from the corner cellin}\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 asouth step from the corner cellin}\mathrm{<mi>\; </mi>}WN\\ \text{to the corner cell in}\mathrm{<mi>\; </mi>}SE\end{array}$

Proof. Similar reasoning as in Theorem 2 (see Figure 13 and Figure 14).

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

Theorem 4. 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)\text{to the 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{to the 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}\mathrm{<mi>\; </mi>}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\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ 2L\text{-pathstartingbyaneaststepfrom}\mathrm{<mi>\; </mi>}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to 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}\\ \max \left(W\right)\mathrm{<mi>\; </mi>}\text{to the corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by an east step from the corner cellin}\mathrm{<mi>\; </mi>}WN\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 from the corner cellin}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{to the corner cell}\\ \text{inSE}\end{array}$

Proof. Similar reasoning as in Theorem 2 (see Figure 15 and Figure 16). $\square$

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

Theorem 5. 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{to the 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)\mathrm{<mi>\; </mi>}\\ \text{and}\\ \mathrm{<mi>\; </mi>}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to the corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by an east step from the corner cellin}\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>}\min \left(N\right)\mathrm{<mi>\; </mi>}\text{to 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{to 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{to the corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by asouth step from the corner cellin}\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\text{to}\mathrm{<mi>\; </mi>}\min \left(E\right)\\ \text{and}\\ 2L\text{-pathstartingbyaneaststepfrom}\mathrm{<mi>\; </mi>}\min \left(W\right)\mathrm{<mi>\; </mi>}\text{to 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 the corner cellin}\mathrm{<mi>\; </mi>}WN\\ \text{to the 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)\mathrm{<mi>\; </mi>}\\ \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 from to th ecorner cellin}\mathrm{<mi>\; </mi>}WN\\ \text{to 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 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)\\ \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 to th ecorner cellin}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\\ \text{to the corner cell in}\mathrm{<mi>\; </mi>}SE\\ \text{and}\\ 2L\text{-path starting by asouth step from the corner cellin}\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 asouth step from the corner cellin}\mathrm{<mi>\; </mi>}WN\mathrm{<mi>\; </mi>}\text{tothecornercell}\\ \text{in}\mathrm{<mi>\; </mi>}SE\end{array}$

or

13)

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

Proof. Similar reasoning as in Theorem 2 (see Figures 17-20). $\square$

Corollary 5. If P satisfies the conditions of Theorem 5, then P is in the class ${\chi }_{2L}^{\mathrm{1,1}}$ and hence in the class ${\alpha }_{2L}^{\mathrm{1,1}}$ .

4. Final Comments

This study showed that 32 geometries are necessary to characterize all 2-convex polyominoes in the class ${\alpha }^{\mathrm{1,1}}$ where the upper left corner and the lower right corner each contains only one cell. Also this study is a theoretical step for the reconstruction of the sub-class ${\alpha }_{2L}^{\mathrm{1,1}}$ . In the spirit of discrete tomography, the design of a reconstruction algorithm for such polyominoes would be the subject of a future article.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Tawbe, K., Ghandour, N. and Atwi, A. (2019) 2-Convex Polyominoes: Non-Empty Corners. Open Journal of Discrete Mathematics, 9, 33-51. https://doi.org/10.4236/ojdm.2019.92005

References