Research ArticleOpen AccessGoogle Scholar indexed
<i>L</i>-Convex Polyominoes: Discrete Tomographical Aspects
Department of Mathematics, Lebanese University, Beirut, Lebanon
Department of Mathematics & Physics, Lebanese International University, Beirut, Lebanon
- 1 Department of Mathematics, Lebanese University, Beirut, Lebanon
- 2 Department of Mathematics & Physics, Lebanese International University, Beirut, Lebanon
Open Journal of Discrete Mathematics·Volume 08 (2018)·Pages 116–136·Published 26 September 2018·DOI10.4236/ojdm.2018.84009
Copy link · social · email
Abstract
This paper uses the geometrical properties of L -convex polyominoes in order to reconstruct these polyominoes. The main idea is to modify some clauses to the original construction of Chrobak and Dürr in order to control the L -convexity using 2SAT satisfaction problem.
KeywordsConvex PolyominoesMonotone PathsDiscrete Geometry
- 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. https://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. https://doi.org/10.1016/j.ejc.2006.06.020
- Castiglione, G. and Restivo, A. (2003) Reconstruction of L-Convex Polyominoes. Electronic Notes on Discrete Mathematics, 12, 290-301. https://doi.org/10.1016/S1571-0653(04)00494-9
- Chrobak, M. and Durr, 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
- Castiglione, G., Frosini, A., Restivo, A. and Rinaldi, S. (2005) A Tomographical Characterization of L-Convex Polyominoes. Lecture Notes in Computer Sciense, Vol. 3429. Proceedings of 12th International Conference on Discrete Geometry Fir Computer Imagery, DGCI, Poitiers, 2005, 115-125.
- Tawbe, K. and Vuillon, L. (2011) 2L-Convex Polyominoes: Geometrical Aspects. Contributions to Discrete Mathematics, 6.