L-Convex Polyominoes: Geometrical Aspects

Khalil Tawbe^1,2, S. Mansour²

¹Department of Mathematics, Lebanese University, Beirut, Lebanon.
²Department of Mathematics, Lebanese International University, Beirut, Lebanon.

DOI: 10.4236/am.2019.108046                

Abstract

A polyomino P is called L-convex if for every two cells there exists a monotone path included in P with at most one change of direction. This paper is a theoretical step for the reconstruction of all L-convex polyominoes by using the geometrical paths. First we investigate the geometrical properties of all subclasses of non-directed L-convex polyominoes by giving nine geometries that characterize all non-directed L-convex polyominoes. Finally, we study the subclasses of directed L-convex polyominoes and we give necessary and sufficient conditions for polyominoes to be L-convex.

Keywords

Discrete Geometry, Monotone Paths, L-Convex Polyominoes

1. Introduction

A planar discrete set is a finite subset of the integer lattice ${\mathbb{N}}^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 [1] (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).

A directed polyomino is obtained by starting out from a cell called source and by adding some other cells in two pre-determined directions, for example east and south, that is, to the right of, or below, the existing cells. A directed convex polyomino is a directed polyomino having connected columns and rows (see Figure 3).

Figure 1. A finite set of $\mathbb{N}\times \mathbb{N}$ , and its representation in terms of a binary matrix and a set of cells.

Figure 2. Row convex and convex polyomino.

Figure 3. A directed convex polyomino.

In this paper we study the geometrical aspects of a particular family of convex polyominoes, introduced in [2] as the first level in a classification of convex polyominoes and called L-convex. In [2] the authors observed that L-convex polyominoes have the property that every pair of cells is connected by a monotone path involving at most one direction. In this way each convex polyomino is characterized by a parameter k that represents the maximum number of changes of direction in these paths. More precisely, a convex polyomino is called k-convex if, for every pair of its cells, there is at least a monotone path with at most k changes of direction that connects them. When the value of k is 1 we have the so-called L-convex polyominoes.

This class of polyominoes has been considered from different points of view. In [3] combinatorial aspects of L-convex polyominoes are analyzed, giving the enumeration according to the semiperimeter and the area. In [2] it is given an algorithm that reconstructs an L-convex polyomino from the set of its maximal L-polyominoes. Similarly in [4] it is given another way to reconstruct an L-convex polyomino from the size of some special paths, called bordered L-paths.

A problem frequently studied in literature is the reconstruction of a discrete set, on which some connectivity constraints are imposed, from partial informations. In particular, Discrete Tomography considers the problem of reconstructing a discrete set from measurements, generically known as projections, of the number of cells in the set that lie on lines with fixed scopes. In the special case of a convex polyomino P, one considers orthogonal (horizontal and vertical) projections, i.e. the pair $\left(H\mathrm{,}V\right)$ that gives the number of cells in each column and row of P, respectively. In [5] it is proved that each L-convex polyominoes P is uniquely determined by its horizontal and vertical projections while the same does not hold, in general, for convex polyominoes. Such projections may be seen as sizes (number of cells) of vertical and horizontal straight paths connecting cells of the opposite borders of P.

This paper is divided into 5 sections. After basics on polyominoes, we investigate in Section 3 the geometrical properties between the feet of all subclasses of non-directed L-convex polyominoes by giving nine geometries. Then these geometries are simplified to four by creating the link between all of them. Finally, using these four geometries we give a theorem that allows us to control the L-convexity of all non-directed convex polyominoes. In Section 4, we introduce the properties of all subclasses of directed L-convex polyominoes and we give the conditions of the L-convexity. A final comment on these geometrical properties is given in Section 5.

2. Definitions and Notations

To each discrete set S, represented as an $m\times n$ binary matrix, we associate two integer vectors $H=\left(h_1\mathrm{,}\cdots \mathrm{,}{h}_m\right)$ and $V=\left(v_1\mathrm{,}\cdots \mathrm{,}{v}_n\right)$ 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 [1] . The vectors H and V are called the horizontal and vertical projections of S, respectively (see Figure 4). By convention, the origin of the matrix (that is the cell with coordinates $\left(\mathrm{1,1}\right)$ ) is in the upper left position.

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 $\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$ , 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 [1] :

Figure 4. A polyomino P with $H=\left(3,4,6,5,2\right)$ and $V=\left(1,3,4,5,4,1\right)$.

• 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$.

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{.}$

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

Proposition 1 (Gastiglione, Restivo). [2] A polyomino P is convex if and only if every pair of cells is connected by a monotone path.

3. Geometrical Properties L-Convex Polyominoes

In this section, we investigate the geometrical properties of L-convex polyominoes in terms of monotone paths.

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 [6] ). 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)$ ) [1] (see Figure 5).

Definition 1. 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 [1] .

Proposition 2. 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)$. If $H=\left(n\mathrm{,}{h}_2\mathrm{,}\cdots \mathrm{,}{h}_m\right)$ or $H=\left(h_1,h_2,\cdots ,n\right)$ or $V=\left(m\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right)$ or $V=\left(v_1,v_2,\cdots ,m\right)$ then P is an L-convex polyomino.

Proof. Let P be a convex polyomino such that $H=\left(n,h_2,\cdots ,h_m\right)$ (see Figure 6), then the bar allows us to go from the first cell situated at the position $\left(\mathrm{1,1}\right)$ to all other cells with at most one change of direction. Thus every two cells is connected by a monotone path with at most one change of direction and hence P is an L-convex polyomino. (Similar reasoning holds for the other three cases). $\square$

Let $\mathcal{C}$ (resp. ${\mathcal{C}}_L$ ) be the class of convex polyominoes (resp. L-convex polyominoes) and let P be in $\mathcal{C}$ (resp. ${\mathcal{C}}_L$ ) such that P does not satisfy Proposition 2. Also suppose that P is not a directed polyomino, then one can define the following subclasses of convex polyominoes:

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

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

Figure 5. Min and max of the four feet.

Figure 6. An L-convex polyomino with $H=\left(7,6,5,3,2\right)$.

• $\begin{array}{c}\gamma =\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(\min \left(N\right)<\min \left(S\right)\text{or}\min \left(N\right)>\min \left(S\right)\right)\\ \text{and}\min \left(W\right)=\min \left(E\right)\}\end{array}$.

• $\begin{array}{l}\mu =\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(\min \left(N\right)<\min \left(S\right)\text{or}\min \left(N\right)>\min \left(S\right)\right)\\ \mathrm{<mi>\; </mi>}\text{and}\left(\min \left(W\right)<\min \left(E\right)\text{or}\min \left(W\right)>\min \left(E\right)\right)\}\end{array}$.

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

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

• $\begin{array}{l}{\gamma }_L=\{P\in {\mathcal{C}}_L\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(\min \left(N\right)<\min \left(S\right)\text{or}\min \left(N\right)>\min \left(S\right)\right)\\ \mathrm{<mi>\; </mi>}\text{and}\min \left(W\right)=\min \left(E\right)\}\end{array}$.

• $\begin{array}{l}{\mu }_L=\{P\in {\mathcal{C}}_L\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(\min \left(N\right)<\min \left(S\right)\text{or}\min \left(N\right)>\min \left(S\right)\right)\\ \text{and}\left(\min \left(W\right)<\min \left(E\right)\text{or}\min \left(W\right)>\min \left(E\right)\right)\end{array}$ (see Figure 7).

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\}$.

Figure 7. Four L-convex polyominoes where (a): an element of the class ${\alpha }_L$ , (b): an element of the class ${\beta }_L$ , (c): an element of the class ${\gamma }_L$ , and (d): an element of the class ${\mu }_L$.

The following characterizations hold for convex polyominoes in the class ${\mu }_L,{\alpha }_L\mathrm{,}{\beta }_L$ and ${\gamma }_L$.

Proposition 3. Let P be an L convex polyomino in the class ${\mu }_L$ (resp. ${\alpha }_L\mathrm{,}{\beta }_L$ and ${\gamma }_L$ ), then there exists an L-path from $\min \left(N\right)$ to $\max \left(E\right)$ with a south step followed by an east step, and an L-path from $\min \left(W\right)$ to $\max \left(S\right)$ with an east step followed by a south step.

Proof. It is an immediate result from the fact that P is an L-convex and P is not a directed polyomino (see Figure 7). $\square$

Proposition 4. Let P be an L-convex polyomino in the class ${\alpha }_L$ , then the feet of P are connected by at least an L-path from $\min \left(N\right)$ to $\max \left(S\right)$ with a south step followed by an east step, and an L-path from $\min \left(W\right)$ to $\max \left(E\right)$ with an east step followed by a south step (see Figure 8).

Proof. It is an immediate result from the fact that P is an L-convex and P is not a directed polyomino (see Figure 8). $\square$

Proposition 5. Let P be an L-convex polyomino in the class ${\beta }_L$ , then at least one of the two following affirmations is true.

1) The feet of P are connected by an L-path from $\min \left(N\right)$ to $\max \left(S\right)$ with a south step followed by an east step and an L-path from $\min \left(W\right)$ to $\max \left(E\right)$ with a south step followed by an east step.

2) The feet of P are connected by an L-path from $\min \left(N\right)$ to $\max \left(S\right)$ with a south step followed by an east step and an L-path from $\max \left(W\right)$ to $\min \left(E\right)$ with an east step followed by a north step (see Figure 9).

Proof. Here the result comes from the fact that P is an L-convex and P is not a directed polyomino and we consider one of the two cases (1) $\min \left(W\right)<\min \left(E\right)$ or (2) $\min \left(W\right)>\min \left(E\right)$ (see Figure 9). $\square$

Figure 8. The two L-paths between the feet in the class ${\alpha }_L$.

Figure 9. The two different L-paths between the feet in the class ${\beta }_L$.

Proposition 6. Let P be an L-convex polyomino in the class ${\gamma }_L$ , then at least one of the two following affirmations is true.

1) The feet of P are connected by an L-path from $\min \left(W\right)$ to $\max \left(E\right)$ with an east step followed by a south step and an L-path from $\min \left(N\right)$ to $\min \left(S\right)$ with an east step followed by a south step.

2) The feet of P are connected by an L-path from $\min \left(W\right)$ to $\max \left(E\right)$ with an east step followed by a south step and an L-path from $\max \left(N\right)$ to $\min \left(S\right)$ with a south step followed by a west step (see Figure 10).

Proof. Here the result comes from the fact that P is an L-convex and P is not a directed polyomino and we consider one of the two cases 1) $\max \left(S\right)<\max \left(N\right)$ or 2) $\max \left(S\right)>\max \left(N\right)$ (see Figure 10). $\square$

Proposition 7. Let P be an L-convex polyomino in the class ${\mu }_L$ , then at least one of the four following affirmations is true.

1) The feet of P are connected by an L-path from $\min \left(N\right)$ to $\max \left(S\right)$ with an east step followed by a south step and an L-path from $\min \left(W\right)$ to $\max \left(E\right)$ with a south step followed by an east step.

2) The feet of P are connected by an L-path from $\min \left(N\right)$ to $\max \left(S\right)$ with an east step followed by a south step and an L-path from $\max \left(W\right)$ to $\min \left(E\right)$ with an east step followed by a north step.

3) The feet of P are connected by an L-path from $\min \left(W\right)$ to $\max \left(E\right)$ with a south step followed by an east step and an L-path from $\max \left(S\right)$ to $\max \left(N\right)$ with an east step followed by a north step.

4) The feet of P are connected by an L-path from $\max \left(W\right)$ to $\min \left(E\right)$ with an east step followed by a north step and an L-path from $\max \left(S\right)$ to $\max \left(N\right)$ with an east step followed by a north step (see Figure 11).

Figure 10. The two different L-paths between the feet in the class ${\gamma }_L$.

Figure 11. The four different L-paths between the feet in the class ${\mu }_L$.

Proof. Here the result comes from the fact that P is an L-convex and P is not a directed polyomino and we consider one of the four cases (1) $\min \left(W\right)<\min \left(E\right)$ and $\max \left(S\right)<\max \left(N\right)$ or (2) $\min \left(W\right)>\min \left(E\right)$ and $\max \left(S\right)<\max \left(N\right)$ or (3) $\min \left(W\right)<\min \left(E\right)$ and $\max \left(S\right)>\max \left(N\right)$ or (4) $\min \left(W\right)>\min \left(E\right)$ and $\max \left(S\right)>\max \left(N\right)$ (see Figure 11). $\square$

To summarize, if P is an L-convex polyomino (P is not directed), then the feet of P are characterized by the geometries shown in Figure 12.

Proposition 8. Let P be an L-convex polyomino (P is not directed), then the feet of P are connected at least by one of the nine following geometries of the L-paths in Figure 12.

• $\left(2\right)\cap \left(5\right)\in {\alpha }_L$

• $\left(2\right)\cap \left(4\right)\in {\beta }_L$

• $\left(2\right)\cap \left(6\right)\in {\beta }_L$

• $\left(1\right)\cap \left(5\right)\in {\gamma }_L$

• $\left(3\right)\cap \left(5\right)\in {\gamma }_L$

• $\left(1\right)\cap \left(4\right)\in {\mu }_L$

Figure 12. The three types of L-paths between each two opposite feet.

• $\left(1\right)\cap \left(6\right)\in {\mu }_L$

• $\left(3\right)\cap \left(4\right)\in {\mu }_L$

• $\left(3\right)\cap \left(6\right)\in {\mu }_L$.

Proof. This is a direct summary of the last four propositions (see Figure 11). $\square$

Remark 1. The geometries $\left(1\right)\cap \left(4\right)$ , $\left(2\right)\cap \left(5\right)$ , $\left(2\right)\cap \left(6\right)$ , and $\left(3\right)\cap \left(5\right)$ mentioned in Proposition 8 give directly the two L-paths mentioned in Proposition 3.

The geometries $\left(2\right)\cap \left(4\right)$ , $\left(3\right)\cap \left(4\right)$ , and $\left(3\right)\cap \left(6\right)$ in Proposition 8 give directly the L-path from $\min \left(N\right)$ to $\max \left(E\right)$ with a south step followed by east step.

The geometries $\left(1\right)\cap \left(5\right)$ and $\left(1\right)\cap \left(6\right)$ in Proposition 8 give directly the L-path from $\min \left(W\right)$ to $\max \left(S\right)$ with an east step followed by a south step.

Now, we define the cells on the SE and WE borders to define the sets $X\mathrm{,}Z\mathrm{,}{X}^{\prime }$ and $Z^{\prime }$ from these cells.

Let P be a convex polyomino in the class $\mu$ (resp. $\alpha \mathrm{,}\beta$ and $\gamma$ ) (P is not directed) and let $I=\left\{\left(i_1,j_1\right),\left(i_2,j_2\right),\cdots ,\left(i_r,j_r\right)\right\}$ be the set of cells belonging to P such that $\left(i_1,j_1\right)=\left(m,\max \left(S\right)\right)$ , $\left(i_r,j_r\right)=\left(\max \left(E\right),n\right)$ , and for $2\le k\le r-1$ , let $\left(i_k\mathrm{,}{j}_k\right)$ be the cells situated on the border of the set SE.

Similarly, let $J=\left\{\left({i^{\prime }}_1,{j^{\prime }}_1\right),\left({i^{\prime }}_2,{j^{\prime }}_2\right),\cdots ,\left({i^{\prime }}_s,{j^{\prime }}_s\right)\right\}$ be the set of cells belonging to P such that such that $\left({i^{\prime }}_1,{j^{\prime }}_1\right)=\left(m\mathrm{,}\min \left(S\right)\right)$ , $\left({i^{\prime }}_s,{j^{\prime }}_s\right)=\left(\max \left(W\right)\mathrm{,1}\right)$ , and for $2\le l\le s-1$ , let $\left({i^{\prime }}_l,{j^{\prime }}_l\right)$ be the cells situated on the border of the set WS.

Now let $X=\left\{x_1,\cdots ,x_k,\cdots ,x_r\right\}$ be the set of cells such that $x_1=\left(m-v_{\max \left(S\right)}+1,\max \left(S\right)\right)$ , $\cdots$ , $x_k=\left(i_k-v_{j_k}+1,j_k\right)$ , $\cdots$ , $x_r=\left(\min \left(E\right),n\right)$ and $Z=\left\{z_1,\cdots ,z_k,\cdots ,z_r\right\}$ be the set of cells such that $z_1=\left(m,\min \left(S\right)\right)$ , $\cdots$ , $z_k=\left(i_k,j_k-h_{i_k}+1\right)$ , $\cdots$ , $z_r=\left(\max \left(E\right),n-h_{\max \left(E\right)}+1\right)$.

Similarly, let $X^{\prime }=\left\{{x^{\prime }}_1\mathrm{,}\cdots \mathrm{,}{x^{\prime }}_l\mathrm{,}\cdots \mathrm{,}{x^{\prime }}_s\right\}$ be the set of cells such that ${x^{\prime }}_1=\left(m-v_{\min \left(S\right)}+1,\min \left(S\right)\right)$ , $\cdots$ , ${x^{\prime }}_l=\left(i_l-v_{j_l}+1,j_l\right)$ , $\cdots$ , ${x^{\prime }}_s=\left(\min \left(W\right),1\right)$ and $Z^{\prime }=\left\{{z^{\prime }}_1\mathrm{,}\cdots \mathrm{,}{z^{\prime }}_l\mathrm{,}\cdots \mathrm{,}{z^{\prime }}_s\right\}$ be the set of cells such that ${z^{\prime }}_1=\left(m,\max \left(S\right)\right)$ , $\cdots$ , ${z^{\prime }}_l=\left({i^{\prime }}_l,j_l+h_{i_l}-1\right)$ , $\cdots$ , ${z^{\prime }}_s=\left(\max \left(W\right),1+h_{\max \left(W\right)}-1\right)$ (see Figure 13).

Theorem 1. Let P be a convex polyomino such that P satisfies at least one of the following geometries

Figure 13. Red cells are the cells situated on the border of SE and WS with $\left(m\mathrm{,}\max \left(S\right)\right)$ , $\left(\max \left(E\right)\mathrm{,}n\right)$ , $\left(m\mathrm{,}\min \left(S\right)\right)$ and $\left(\max \left(W\right)\mathrm{,1}\right)$.

• $\left(2\right)\cap \left(5\right)\in \alpha$

• $\left(2\right)\cap \left(4\right)\in \beta$

• $\left(2\right)\cap \left(6\right)\in \beta$

• $\left(1\right)\cap \left(5\right)\in \gamma$

• $\left(3\right)\cap \left(5\right)\in \gamma$

• $\left(1\right)\cap \left(4\right)\in \mu$

• $\left(1\right)\cap \left(6\right)\in \mu$

• $\left(3\right)\cap \left(4\right)\in \mu$

• $\left(3\right)\cap \left(6\right)\in \mu$.

Then P is an L-convex polyomino if and only if for $2\le k\le r-1$ , $2\le l\le s-1$ the cells situated at the positions $\left(m-v_{\max \left(S\right)},\min \left(S\right)-1\right)$ , $\cdots$ , $\left(i_k-v_{j_k},j_k-h_{i_k}\right)$ , $\cdots$ , $\left(\min \left(E\right)-1,n-h_{\max \left(E\right)}\right)$ and $\left(m-v_{\min \left(S\right)},\max \left(S\right)+1\right)$ , $\cdots$ , $\left(i_l-v_{j_l},j_l+h_{i_l}\right)$ , $\cdots$ , $\left(\min \left(W\right)-1,1+h_{\max \left(W\right)}\right)$ do not belong to P.

Proof. Suppose that P is a convex polyomino. The intersections control the geometries and the L-path between feet.

$\Rightarrow$ If P is an L-convex then obviously the cells situated at the positions $\left(m-v_{\max \left(S\right)},\min \left(S\right)-1\right)$ , $\cdots$ , $\left(i_k-v_{j_k},j_k-h_{i_k}\right)$ , $\cdots$ , $\left(\min \left(E\right)-1,n-h_{\max \left(E\right)}\right)$ and $\left(m-v_{\min \left(S\right)},\max \left(S\right)+1\right)$ , $\cdots$ , $\left(i_l-v_{j_l},j_l+h_{i_l}\right)$ , $\cdots$ , $\left(\min \left(W\right)-1,1+h_{\max \left(W\right)}\right)$ do not belong to P. Indeed, these cells could be attained only by using a 2L-path from the SE or WS borders.

$\Leftarrow$ The cells situated at the positions $\left(m-v_{\max \left(S\right)},\min \left(S\right)-1\right)$ , $\cdots$ , $\left(i_k-v_{j_k},j_k-h_{i_k}\right)$ , $\cdots$ , $\left(\min \left(E\right)-1,n-h_{\max \left(E\right)}\right)$ and $\left(m-v_{\min \left(S\right)},\max \left(S\right)+1\right)$ , $\cdots$ , $\left(i_l-v_{j_l},j_l+h_{i_l}\right)$ , $\cdots$ , $\left(\min \left(W\right)-1,1+h_{\max \left(W\right)}\right)$ control maximal rectangles from SE and WS. Thus, they control the L-convexity of the polyomino (see Figure 14).

Figure 14. An L-convex polyomino satisfying Theorem 1.

4. Directed L-Convex Polyominoes

Let P be a convex polyomino such that P does not satisfy Proposition 2. From the definition of directed convex polyominoes, let us define the following classes.

• $\delta =\left\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(1,\min \left(N\right)\right)=\left(\min \left(W\right),1\right)\right\}$.

• $\psi =\left\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(\max \left(W\right),1\right)=\left(m,\min \left(S\right)\right)\right\}$.

• ${\delta }^{\prime }=\left\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(m,\max \left(S\right)\right)=\left(\max \left(E\right),n\right)\right\}$.

• ${\psi }^{\prime }=\left\{P\in \mathcal{C}\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(1,\max \left(N\right)\right)=\left(\min \left(E\right),n\right)\right\}$.

• ${\delta }_L=\left\{P\in {\mathcal{C}}_L\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(1,\min \left(N\right)\right)=\left(\min \left(W\right),1\right)\right\}$ (see Figure 15).

• ${\psi }_L=\left\{P\in {\mathcal{C}}_L\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(\max \left(W\right),1\right)=\left(m,\min \left(S\right)\right)\right\}$.

• ${{\delta }^{\prime }}_L=\left\{P\in {\mathcal{C}}_L\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(m,\max \left(S\right)\right)=\left(\max \left(E\right),n\right)\right\}$ (see Figure 15).

• ${{\psi }^{\prime }}_L=\left\{P\in {\mathcal{C}}_L\mathrm{<mi>\; </mi>}|\mathrm{<mi>\; </mi>}\left(1,\max \left(N\right)\right)=\left(\min \left(E\right),n\right)\right\}$.

Let us define the horizontal transformation (symmetry)

$S_H\mathrm{<mo>\; :\; </mo>}\left(i\mathrm{,}j\right)\to \left(m-i+\mathrm{1,}j\right)$

which transforms the polyomino P from $\delta$ to $\psi$ , ${\delta }^{\prime }$ to ${\psi }^{\prime }$ , ${\delta }_L$ to ${\psi }_L$ , and ${{\delta }^{\prime }}_L$ to ${{\psi }^{\prime }}_L$. Indeed the transformation acts on the feet of the polyomino as it is shown in the following table (see Table 1). Thus we only investigate the properties of the classes ${\delta }_L$ and ${{\delta }^{\prime }}_L$.

Proposition 9. Let P be an L-convex polyomino in the class ${\delta }_L$ , then there exist two L-paths from $\min \left(N\right)=\min \left(W\right)$ to $\max \left(E\right)$ with a south step followed by an east step, and from $\min \left(N\right)=\min \left(W\right)$ to $\max \left(S\right)$ with an east step followed by a south step.

Proof. The two L-paths control the L-convexity of the feet (see Figure 16). $\square$

Theorem 2. Let P be a convex polyomino in the class $\delta$ such that there exist two L-paths from $\min \left(N\right)=\min \left(W\right)$ to $\max \left(E\right)$ with a south then an east steps, and from $\min \left(N\right)=\min \left(W\right)$ to $\max \left(S\right)$ with an east then a south steps. Then P is an L-convex polyomino if and only if the cell at the position $\left(\max \left(W\right)+\mathrm{1,}\max \left(N\right)+1\right)$ does not belong to P.

Proof. The maximal rectangle from the point $\left(\mathrm{1,1}\right)$ has extremal cells in the position $\left(\max \left(W\right)\mathrm{,}\max \left(N\right)\right)$. That is the point at position

Figure 15. An element of the class ${\delta }_L$ on the left and one of the class ${{\delta }^{\prime }}_L$ on the right.

Figure 16. An L-convex polyomino in the class ${\delta }_L$.

Table 1. The horizontal transformation $S_H$ on the feet of P.

$\left(\max \left(W\right)+\mathrm{1,}\max \left(N\right)+1\right)$

is reachable from cell $\left(\mathrm{1,1}\right)$ by a 2L-path. Thus the point at the position $\left(\max \left(W\right)+\mathrm{1,}\max \left(N\right)+1\right)$ does not belong to P (see Figure 16). $\square$

Proposition 10. Let P be an L-convex polyomino in the class ${{\delta }^{\prime }}_L$ , then there exist two L-paths from $\max \left(E\right)=\max \left(S\right)$ to $\min \left(N\right)$ with a west step followed by a north step, and from $\max \left(E\right)=\max \left(S\right)$ to $\min \left(W\right)$ with a north step followed by a west step.

Theorem 3. Let P be a convex polyomino in the class ${\delta }^{\prime }$ such that there exist two L-paths from $\max \left(E\right)=\max \left(S\right)$ to $\min \left(N\right)$ with a west step followed by a north step, and from $\max \left(E\right)=\max \left(S\right)$ to $\min \left(W\right)$ with a north step followed by a west step. Then P is an L-convex polyomino if and only if the cell at the position $\min \left(E\right)-\mathrm{1,}\min \left(S\right)-1$ does not belong to P (see Figure 17).

Figure 17. An L-convex polyomino in the class ${{\delta }^{\prime }}_L$.

5. Conclusion

In this paper we studied the geometrical properties of all subclasses of directed and non-directed L-convex polyominoes and we gave necessary and sufficient conditions to characterize them. The results of this paper will be used in order to reconstruct all L-convex polyominoes using geometrical paths. This paper may help us to understand the geometrical behavior of kL-convex polyominoes and hence find a way to reconstruct them all.

Conflicts of Interest

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

References

[1]	Tawbe, K. and Vuillon, L. (2011) 2L-Convex Polyominoes: Geometrical Aspects. Contributions to Discrete Mathematics, North America, 6.
[2]	Castiglione, G. and Restivo, A. (2003) Reconstruction of L-Convex Polyominoes. Electronic Notes in Discrete Mathematics, 12, 290-301. https://doi.org/10.1016/S1571-0653(04)00494-9
[3]	Castiglione, G., Frosini, A., Munarini, E., Restivo, A. and Rinaldi, S. (2007) Combinatorial Aspects of L-Convex Polyominoes. European Journal of Combinatorics, 28, 1724-1741. https://doi.org/10.1016/j.ejc.2006.06.020
[4]	Castiglione, G., Restivo, A. and Vaglica, R. (2006) A Reconstruction Algorithm for L-Convex Polyominoes. Theoretical Computer Science, 356, 58-72. http://www.sciencedirect.com https://doi.org/10.1016/j.tcs.2006.01.045
[5]	Castiglione, G., Frosini, A., Restivo, A. and Rinaldi, S. (2005) A Tomographical Characterization of L-Convex Polyominoes. Lecture Notes in Computational Science, Vol. 3429. Proceedings of 12th International Conference on Discrete Geometry Fir Computer Imagery, Poitiers, 11-13 April 2005, 115-125. https://doi.org/10.1007/978-3-540-31965-8_11
[6]	Barcucci, E., Del Lungo, A., Nivat, M. and Pinzani, R. (1996) Reconstructing Convex Polyominoes from Horizontal and Vertical Projections. Theoretical Computer Science, 155, 321-347. https://doi.org/10.1016/0304-3975(94)00293-2