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
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
. In the third section, 32 geometries in the class
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
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
binary matrix, two integer vectors
and
are associated such that, for each
,
and
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
![]()
Figure 1. A representation of a finite set of
.
![]()
Figure 2. Row convex and convex polyomino.
![]()
Figure 3. A polyomino P with
and
.
as horizontal and vertival projections, respectively, then we say that S satisfies (H,V). Using the usual matrix notations, the element
denotes the entry in row i and column j.
For any two cells
and
in a polyomino P, a path from A to B, is a sequence of adjacent disjoint cells belonging to P. For each
, we say that the two consecutive cells
form:
• an east step if
and
;
• a north step if
and
;
• a west step if
and
;
• a south step if
and
.
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
, for
, if
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).
![]()
Figure 4. The convex polyomino on the left is 2-convex, while the one on the right is 1-convex.
3. Geometrical Aspects
In this section, we study the geometrical aspects of 2-convex polyominoes in terms of positions of the feet. Let
be two vectors of projections, and let P be a convex polyomino that satisfies
. By a classical argument, P is contained in a rectangle R of size
(called minimal bounding box). Let
(
,
,
) be the intersection of P's boundary on the lower (right, upper, left) side of R (see [1] ). By abuse of notation, for each
and
, we call
[resp.
,
,
] the cell at the position
[resp.
,
,
] and
[resp.
,
,
] the cell at the position
[resp.
,
,
] (see Figure 5) (see [4]).
Definition 3. The segment
is called the S-foot. Similarly, the segments
,
and
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
be the class of convex polyominoes thus we have two classes of polyominoes regarding the position of the non-intersecting feet.
•
•
.
Let us define the horizontal transformation (symmetry) [4]
which transforms the polyomino P from the class
to the class
(see Figure 7).
The study of the classes
and
is very complicated until now. So we make the choice of studying one special case called
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
![]()
Figure 5. The four feet in the rectangle R.
![]()
Figure 6. A v-centered polyomino on the left and an h-centered polyomino on the right.
![]()
Figure 7. The horizontal transformation SH on the feet of P.
![]()
Figure 8. An element of the class
on the left and of the class
on the right.
describe the geometries of 2-convex polyominoes in the class
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] :
•
,
•
,
•
,
•
.
The above sets with the classes
and
allow us to define the following two classes:
•
, (see Figure 8)
•
, (see Figure 8)
•
, where P is a 2-convex polyomino.
•
, where P is a 2-convex polyomino.
Note that the horizontal symmetry
maps
to
.
The following characterization holds for convex polyominoes in the class
.
Theorem 1. Let P be a convex polyomino in the class
, P is 2-convex if and only if there exist nine paths:
1) from
to
,
2) and from
to
,
3) and from
to
,
4) and from
to
,
5) and from the corner cell in WN to
,
6) and from the corner cell in WN to
,
7) and from
to the corner cell in SE,
8) and from
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
and
such that any path between them has more than two changes of direction. Let us suppose that
is at the position
and
is at the position
(the other positions are similar). We have the following cases.
CASE 1:
If the path from
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
and
, hence the contradiction.
CASE 2:
If the path from
to the corner cell in SE has two changes of direction, one can observe the following cases.
• Either the path goes through
and then there exist an L-path between
and
, thus by convexity there exists a 2L-path from
to
, hence the contradiction; or
• The path goes through
and then there is an L-path between
and the corner cell in SE, thus there exists a 2L-path from
to
, hence the contradiction; or
• The path goes through
and then there is an L-path between
and the corner cell in SE, thus there exists a 2L-path from
to
, hence the contradiction; or
• The path goes through a path where its vertical position is between
and
, thus there exists a 2L-path from
to
, hence the contradiction (see Figure 9).
The cases (1), (2), (3), (4), (5), (6), (7) are similar up to symmetry.
Corollary 1. If P satisfies Theorem 1, then P is in the class
(see Figure 10).
![]()
Figure 9. L-path and 2L-paths between
and the corner cell in SE.
![]()
Figure 10. An element of the class
.
Now in order to understand the different geometries of the class
let us define the following subclasses of the class
:
•
(see Figure 11).
•
. (see Figure 11).
•
(see Figure 11).
•
(see Figure 11).
•
, where P is a 2-convex polyomino.
•
, where P is a 2-convex polyomino.
![]()
Figure 11. An element of the class: (a)
; (b)
; (c)
; (d)
.
•
, where P is a 2-convex polyomino.
•
, where P is a 2-convex polyomino.
Theorem 2. Let P be a convex polyomino in the class
, P is 2-convex if and only if there exists an L-path from
1)
or
2)
or
3)
or
4)
Proof. (Ü) Suppose that P satisfies only the first geometry, i.e. there exist L-paths from
to
and from the corner cell in WN to
. From the first L-path, one can deduce that there exist 2L-paths from
to
, from
to
and from
to the corner cell in SE. Now from the second L-path, one can deduce that there exist 2L-paths from
to
, from
to
, from
to the corner cell in SE, from the corner cell in WN to
, from the corner cell in WN to
, 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
to
, from
to
, from
to the corner cell in SE, from
to the corner cell in SE, from the corner cell in WN to
, and from the corner cell in WN to
. 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
to the corner cell in SE and from
to
. From the first L-path, one can deduce that there exists an L-path between
and the corner cell in SE. From the second L-path, one can see that there is no information between
and
, hence P is not 2L-convex polyomino.
2) There exist L-paths from the corner cell in WN to
and from
to
. From the first L-path, one can deduce that there is an L-path between the corner cell in WN to
. From the second L-path, one can see that there is no information between
and
, hence P is not 2L-convex polyomino.
3) There exist L-paths from
to the corner cell in SE and from
to
. From the first L-path, one can deduce that there exists an L-path between
and the corner cell in SE. From the second L-path, one can see that there is no information between
and
, hence P is not 2L-convex polyomino.
4) There exist L-paths from the corner cell in WN to
and from
to
. From the first L-path, one can deduce that there is an L-path between the corner cell in WN to
. From the second L-path, one can see that there is no information between
and
, hence P is not 2L-convex polyomino.
![]()
Figure 12. The four geometries in the class
.
In conclusion, the four geometries are necessary to characterize a 2L-convex polyomino in the class
(see Figure 12).
Corollary 2. If P satisfies the conditions of Theorem 2, then P is in the class
and hence in the class
.
Theorem 3. Let P be a convex polyomino in the class
, P is 2-convex if and only if there exists an L-path from
1)
or
2)
or
3)
or
4)
or
5)
or
6)
or
7)
Proof. Similar reasoning as in Theorem 2 (see Figure 13 and Figure 14).
![]()
Figure 13. The first four geometries in the class
.
![]()
Figure 14. The last three geometries in the class
.
Corollary 3. If P satisfies the conditions of Theorem 3, then P is in the class
and hence in the class
.
Theorem 4. Let P be a convex polyomino in the class
, P is 2-convex if and only if there exists an L-path from
1)
or
2)
or
3)
or
4)
or
5)
or
6)
or
7)
Proof. Similar reasoning as in Theorem 2 (see Figure 15 and Figure 16).
Corollary 4. If P satisfies the conditions of Theorem 4, then P is in the class
and hence in the class
.
![]()
Figure 15. The first four geometries in the class
.
![]()
Figure 16. The last three geometries in the class
.
Theorem 5. Let P be a convex polyomino in the class
, P is 2-convex if and only if there exists an L-path from
1)
or
2)
or
3)
or
4)
or
5)
or
6)
or
7)
or
8)
or
9)
or
10)
or
11)
or
12)
or
13)
or
14)
Proof. Similar reasoning as in Theorem 2 (see Figures 17-20).
![]()
Figure 17. The first four geometries in the class
.
![]()
Figure 18. The second four geometries in the class
.
![]()
Figure 19. The third four geometries in the class
.
![]()
Figure 20. The last two geometries in the class
.
Corollary 5. If P satisfies the conditions of Theorem 5, then P is in the class
and hence in the class
.
4. Final Comments
This study showed that 32 geometries are necessary to characterize all 2-convex polyominoes in the class
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
. In the spirit of discrete tomography, the design of a reconstruction algorithm for such polyominoes would be the subject of a future article.