Research ArticleOpen AccessGoogle Scholar indexed
Reconstruction of 2-Convex Polyominoes with Non-Empty Corners
Department of Mathematics, Lebanese University, Beirut, Lebanon
Department of Mathematics, Lebanese International University, Beirut, Lebanon
Department of Mathematics, The International University of Beirut, Beirut, Lebanon
- 1 Department of Mathematics, Lebanese University, Beirut, Lebanon
- 2 Department of Mathematics, Lebanese International University, Beirut, Lebanon
- 3 Department of Mathematics, The International University of Beirut, Beirut, Lebanon
Open Journal of Discrete Mathematics·Volume 09 (2019)·Pages 83–109·Published 9 August 2019·DOI10.4236/ojdm.2019.94009
Copy link · social · email
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.
KeywordsPolyominoConvex ObjectsMonotone Path
- 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
- 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
- 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
- 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.
- 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
- 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
- Tawbe, K. and Vuillon, L. (2011) 2L-Convex Polyominoes: Geometrical Aspects. Contributions to Discrete Mathematics, North America, 6, 1-25.
- 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
- Tawbe, K., Ghandour, N. and Atwi, A. (2019) 2-Convex Polyominoes: Non-Empty Corners. Open Journal of Discrete Mathematics, 9, 33-51.
- Tawbe, K. and Vuillon, L. (2011) 2L-Convex Polyominoes: Tomographical Aspects. Contributions to Discrete Mathematics, 8, 1-12.
- 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
- 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