Reconstruction of 2-Convex Polyominoes with Non-Empty Corners

Khalil  Tawbe; Salwa  Mansour

doi:10.4236/ojdm.2019.94009

Khalil Tawbe^1,2, Salwa Mansour³

Abstract: This paper uses the theoretical material developed in a previous study by the authors in order to reconstruct a subclass of 2-convex polyominoes called

where the upper left corner and the lower right corner of the polyomino contain each only one cell. The main idea is to control the shape of these polyominoes by using 32 types of geometries. Some modifications are made in the reconstruction algorithm of Chrobak and Dürr for HV-convex polyominoes in order to impose these geometries.

Keywords: Polyomino, Convex Objects, Monotone Path

Cite this paper: Tawbe, K. , Mansour, S. (2019) Reconstruction of 2-Convex Polyominoes with Non-Empty Corners. Open Journal of Discrete Mathematics, 9, 83-109. doi: 10.4236/ojdm.2019.94009.

References

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

[2] Brunetti, S. and Daurat, A. (2005) Random Generation of Q-Convex Sets. Theoretical Computer Science, 347, 393-414.
https://doi.org/10.1016/j.tcs.2005.06.033

[3] 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

[4] 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.

[5] Castiglione, G. and Restivo, A. (2003) Reconstruction of L-Convex Polyominoes. Electronic Notes in Discrete Mathematics, Vol. 12, Elsevier Science, Amsterdam.
https://doi.org/10.1016/S1571-0653(04)00494-9

[6] Duchi, E., Rinaldi, S. and Schaeffer, G. (2008) The Number of Z-Convex Polyominoes. Advances in Applied Mathematics, 40, 54-72.
https://doi.org/10.1016/j.aam.2006.07.004

[7] Tawbe, K. and Vuillon, L. (2011) 2L-Convex Polyominoes: Geometrical Aspects. Contributions to Discrete Mathematics, North America, 6, 1-25.

[8] Chrobak, M. and Dürr, C. (1999) Reconstructing hv-Convex Polyominoes from Orthogonal Projections. Information Processing Letters, 69, 283-289.
https://doi.org/10.1016/S0020-0190(99)00025-3

[9] Tawbe, K., Ghandour, N. and Atwi, A. (2019) 2-Convex Polyominoes: Non-Empty Corners. Open Journal of Discrete Mathematics, 9, 33-51.

[10] Tawbe, K. and Vuillon, L. (2011) 2L-Convex Polyominoes: Tomographical Aspects. Contributions to Discrete Mathematics, 8, 1-12.

[11] Even, S., Itai, A. and Shamir, A. (1976) On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, 5, 691-703.
https://doi.org/10.1137/0205048

[12] Aspvall, B., Plass, M.F. and Tarjan, R.E. (1979) A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas. Information Processing Letters, 8, 121-123.
https://doi.org/10.1016/0020-0190(79)90002-4