Abstract
We present a characterization of Z-convex polyominoes in terms of pairs of suitable integer vectors. This lets us design an algorithm which generates all Z-convex polyominoes of size n in constant amortized time.
Partially supported by Project M.I.U.R. PRIN 2010-2011: Automi e linguaggi formali: aspetti matematici e applicativi.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Barcucci, E., Frosini, A., Rinaldi, S.: On directed-convex polyominoes in a rectangle. Discrete Mathematics 298(1-3), 62–78 (2005)
Barcucci, E., Lungo, A.D., Nivat, M., Pinzani, R.: Reconstructing Convex Polyominoes from Horizontal and Vertical Projections. Theor. Comput. Sci. 155(2), 321–347 (1996)
Barcucci, E., Lungo, A.D., Pergola, E., Pinzani, R.: ECO: a methodology for the Enumeration of Combinatorial Objects. J. of Diff. Eq. and App. 5, 435–490 (1999)
Battaglino, D., Fedou, J.M., Frosini, A., Rinaldi, S.: Encoding Centered Polyominoes by Means of a Regular Language. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 464–465. Springer, Heidelberg (2011)
Beauquier, D., Nivat, M.: On Translating One Polyomino to Tile the Plane. Discrete & Computational Geometry 6, 575–592 (1991)
Bender, E.A.: Convex n-ominoes. Discrete Math. 8, 219–226 (1974)
Bousquet-Mélou, M.: A method for the enumeration of various classes of column-convex polygons. Discrete Math. 154(1-3), 1–25 (1996)
Brlek, S., Provençal, X., Fedou, J.-M.: On the tiling by translation problem. Discrete Applied Mathematics 157(3), 464–475 (2009)
Brocchi, S., Frosini, A., Pinzani, R., Rinaldi, S.: A tiling system for the class of L-convex polyominoes. Theor. Comput. Sci. 475, 73–81 (2013)
Carli, F.D., Frosini, A., Rinaldi, S., Vuillon, L.: On the Tiling System Recognizability of Various Classes of Convex Polyominoes. Ann. Comb. 13, 169–191 (2009)
Castiglione, G., Frosini, A., Munarini, E., Restivo, A., Rinaldi, S.: Combinatorial aspects of L-convex polyominoes. Eur. J. Comb. 28(6), 1724–1741 (2007)
Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: A Tomographical Characterization of L-Convex Polyominoes. In: Andrès, É., Damiand, G., Lienhardt, P. (eds.) DGCI 2005. LNCS, vol. 3429, pp. 115–125. Springer, Heidelberg (2005)
Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: Enumeration of L-convex polyominoes by rows and columns. Theor. Comput. Sci. 347(1-2), 336–352 (2005)
Castiglione, G., Restivo, A.: Reconstruction of L-convex Polyominoes. Electronic Notes in Discrete Mathematics 12, 290–301 (2003)
Delest, M.P., Viennot, G.: Algebraic Languages and Polyominoes Enumeration. Theor. Comput. Sci. 34, 169–206 (1984)
Duchi, E., Rinaldi, S., Schaeffer, G.: The number of Z-convex polyominoes. Advances in Applied Mathematics 40(1), 54–72 (2008)
Golomb, W.S.: Checker Boards and Polyominoes. The American Mathematical Monthly 61, 675–682 (1954)
Klarner, D.A., Rivest, R.R.: Asymptotic bounds for the number of convex n-ominoes. Discrete Math. 8, 31–40 (1974)
Kuba, A., Balogh, E.: Reconstruction of convex 2D discrete sets in polynomial time. Theor. Comput. Sci. 283(1), 223–242 (2002)
Mantaci, R., Massazza, P.: From Linear Partitions to Parallelogram Polyominoes. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 350–361. Springer, Heidelberg (2011)
Massazza, P.: On the generation of L-convex polyominoes. In: Proc. of GASCom 2012, Bordeaux, June 25-27 (2012)
Massazza, P.: On the Generation of Convex Polyominoes. Discrete Applied Mathematics (to appear)
Massé, A.B., Garon, A., Labbé, S.: Combinatorial properties of double square tiles. Theor. Comput. Sci. 502, 98–117 (2013)
Micheli, A., Rossin, D.: Counting k-Convex Polyominoes. Electr. J. Comb. 20(2) (2013)
Ollinger, N.: Tiling the Plane with a Fixed Number of Polyominoes. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 638–647. Springer, Heidelberg (2009)
Tawbe, K., Vuillon, L.: 2L-convex polyominoes: Geometrical aspects. Contributions to Discrete Mathematics 6(1) (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Castiglione, G., Massazza, P. (2014). An Efficient Algorithm for the Generation of Z-Convex Polyominoes. In: Barneva, R.P., Brimkov, V.E., Šlapal, J. (eds) Combinatorial Image Analysis. IWCIA 2014. Lecture Notes in Computer Science, vol 8466. Springer, Cham. https://doi.org/10.1007/978-3-319-07148-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-07148-0_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07147-3
Online ISBN: 978-3-319-07148-0
eBook Packages: Computer ScienceComputer Science (R0)