L-Convex Polyominoes: Geometrical Aspects

Khalil  Tawbe; S.  Mansour

doi:10.4236/am.2019.108046

Khalil Tawbe^1,2, S. Mansour²

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

Cite this paper: Tawbe, K. and Mansour, S. (2019) L-Convex Polyominoes: Geometrical Aspects. Applied Mathematics, 10, 646-658. doi: 10.4236/am.2019.108046.

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