On counting Z-convex polyominoes

Paolo Massazza

doi:10.2478/puma-2022-0014

.blurhash-client-img { display: none !important; }

On counting Z-convex polyominoes

Pure Mathematics and Applications

Volume 30 (2022): Issue 1 (June 2022)

By: Paolo Massazza

Open Access

|Jun 2022

Abstract

We show a decomposition that allows to compute the number of convex polyominoes of area n and degree of convexity at most 2 (the so-called Z-convex polyominoes) in polynomial time.

References

[1] M. Bousquet-Mélou, Convex polyominoes and heaps of segments, J. Phys. A: Math. Gen., 25 (1992) 1925–1934.10.1088/0305-4470/25/7/031
Search in Google Scholar Back to article
[2] M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons., Discrete Math., 154 (1996) 1–25.
Search in Google Scholar Back to article
[3] G. Castiglione and P. Massazza, An efficient algorithm for the generation of Z-convex polyominoes, IWCIA 2014, Lecture Notes in Comput. Sci., 8466 (2014) 51–61.
Search in Google Scholar Back to article
[4] G. Castiglione and A. Restivo, Reconstruction of L-convex polyominoes, IWCIA 2003, Electron. Notes in Discrete Math., 12 (2003) 290–301.
Search in Google Scholar Back to article
[5] G. Castiglione and A. Restivo, Ordering and convex polyominoes, MCU 2004, Lecture Notes in Comput. Sci., 3354 (2005) 128–139.
Search in Google Scholar Back to article
[6] E. D. Demaine, J. S. B. Mitchell and J. O’Rourke, The Open Problems Project, http://cs.smith.edu/~jorourke/TOPP
Search in Google Scholar Back to article
[7] V. Dorigatti and P. Massazza, On counting L-convex polyominoes, 22nd Italian Conference on Theoretical Computer Science, CEUR Workshop Proceedings, 3072 (2021) 193–198.
Search in Google Scholar Back to article
[8] E. Duchi, S. Rinaldi and G. Schaeffer, The number of Z-convex polyominoes, Adv. in Appl. Math., 40 (2008) 54–72.
Search in Google Scholar Back to article
[9] S. W. Golomb, Checker boards and polyominoes, Amer. Math. Monthly, 61 (1954) 675–682.
Search in Google Scholar Back to article
[10] I. Jensen, Counting polyominoes: a parallel implementation for cluster computing, ICCS 2003, Lecture Notes in Comput. Sci. 2659 (2003) 203–212.10.1007/3-540-44863-2_21
Search in Google Scholar Back to article
[11] A. Del Lungo, M. Nivat, R. Pinzani and S. Rinaldi, A bijection for the total area of parallelogram polyominoes, Discret. Appl. Math., 144 (2004) 291–302.
Search in Google Scholar Back to article
[12] K. Tawbe and L. Vuillon, 2L-convex polyominoes: geometrical aspects, Contrib. Discrete Math., 6 (2011) 1–25.
Search in Google Scholar Back to article