{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T10:36:40Z","timestamp":1760524600960},"reference-count":21,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T00:00:00Z","timestamp":1711411200000},"content-version":"vor","delay-in-days":85,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2024,2,23]]},"published-print":{"date-parts":[[2024]]},"abstract":"<jats:p>The degree of convexity of a convex polyomino <jats:italic>P<\/jats:italic> is the smallest integer <jats:italic>k<\/jats:italic> such that any two cells of <jats:italic>P<\/jats:italic> can be joined by a monotone path inside <jats:italic>P<\/jats:italic> with at most <jats:italic>k<\/jats:italic> changes of direction. In this paper we show that one can compute in polynomial time the number of polyominoes of area <jats:italic>n<\/jats:italic> and degree of convexity at most 2 (the so-called Z-convex polyominoes). The integer sequence that we have computed allows us to conjecture the asymptotic number <jats:italic>a<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> of Z-convex polyominoes of area <jats:italic>n<\/jats:italic>, <jats:italic>\u0251<\/jats:italic><jats:sub>n<\/jats:sub> \u223c <jats:italic>C<\/jats:italic>\u00b7exp(\u03c0)\u221a11<jats:italic>n<\/jats:italic>\/4\u2044<jats:italic>n<\/jats:italic><jats:sup>3\/2<\/jats:sup>.<\/jats:p>","DOI":"10.1051\/ita\/2024009","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T09:11:28Z","timestamp":1711444288000},"page":"12","source":"Crossref","is-referenced-by-count":1,"title":["Asymptotics of Z-convex polyominoes"],"prefix":"10.1051","volume":"58","author":[{"given":"Anthony J.","family":"Guttmann","sequence":"first","affiliation":[]},{"given":"Paolo","family":"Massazza","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1080\/00029890.1954.11988548","volume":"61","author":"Golomb","year":"1954","journal-title":"Amer. Math. Monthly"},{"key":"R2","unstructured":"O\u2019Rourke J. Demaine E.D. and Mitchell J.S.B., The open problems project."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Jensen I., Counting polyominoes: a parallel implementation for cluster Computing, in Proceedings of the 2003 International Conference on Computational Science: Part III, ICCS\u201903. Springer-Verlag (2003) 203\u2013212.","DOI":"10.1007\/3-540-44863-2_21"},{"key":"R4","doi-asserted-by":"crossref","first-page":"1925","DOI":"10.1088\/0305-4470\/25\/7\/031","volume":"25","author":"Bousquet-M\u00e9lou","year":"1992","journal-title":"J. Phys. A: Math. Gen."},{"key":"R5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0012-365X(95)00003-F","volume":"154","author":"Bousquet-M\u00e9lou","year":"1996","journal-title":"Discrete Math."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Castiglione G. and Restivo A., Ordering and convex polyominoes, in MCU 2004. Vol. 3354 of Lecture Notes in Computer Science. Springer (2005) 128\u2013139.","DOI":"10.1007\/978-3-540-31834-7_10"},{"key":"R7","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.dam.2003.11.007","volume":"144","author":"Del Lungo","year":"2004","journal-title":"Discret. Appl. Math."},{"key":"R8","unstructured":"Klarner D.A., Golomb S.W. and Barequet G., Polyominoes, in Handbook of Discrete and Computational Geometry, edited by Goodman J.E., O\u2019Rourke J. and Toth C.D.. CRC Press, Boca Raton, FL (2017) 359\u2013380."},{"key":"R9","first-page":"1","volume":"11","author":"Del Lungo","year":"2004","journal-title":"Electron. J. Comb."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Del Lungo A., Frosini A. and Rinaldi S., Eco method and the exhaustive generation of convex polyominoes, in DMTC 2003. Vol. 6795 of Lecture Notes in Computer Science. Springer (2003) 129\u2013140.","DOI":"10.1007\/3-540-45066-1_10"},{"key":"R11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.endm.2017.05.007","volume":"59","author":"Formenti","year":"2017","journal-title":"Electron. Notes in Discrete Math."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Formenti E. and Massazza P., On the generation of 2-polyominoes, in DCFS 2018. Vol. 10952 of Lecture Notes in Computer Science. Springer (2018) 101\u2013113.","DOI":"10.1007\/978-3-319-94631-3_9"},{"key":"R13","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.aam.2006.07.004","volume":"40","author":"Duchi","year":"2008","journal-title":"Adv. Appl. Math."},{"key":"R14","first-page":"1","volume":"6","author":"Tawbe","year":"2011","journal-title":"Contrib. Discret. Math."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Castiglione G. and Massazza P., An efficient algorithm for the generation of Z-convex polyominoes, in IWCIA 2014. Vol. 8466 of Lecture Notes in Computer Science. Springer (2014) 51\u201361.","DOI":"10.1007\/978-3-319-07148-0_6"},{"key":"R16","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1016\/S1571-0653(04)00494-9","volume":"12","author":"Castiglione","year":"2003","journal-title":"Electron. Notes Discrete Math."},{"key":"R17","unstructured":"Stanley R.P., Enumerative combinatorics. Vol. 1 of Cambridge Studies in Advanced Mathematics, 2nd edn. Cambridge University Press (2011)."},{"key":"R18","unstructured":"Guttmann A.J. and Kotesovec V., L-convex polyominoes and 201-avoiding ascent sequences, 2021."},{"key":"R19","doi-asserted-by":"crossref","first-page":"045209","DOI":"10.1088\/1751-8113\/48\/4\/045209","volume":"48","author":"Guttmann","year":"2015","journal-title":"J. Phys. A: Math. Theoret."},{"key":"R20","doi-asserted-by":"crossref","first-page":"415002","DOI":"10.1088\/1751-8113\/49\/41\/415002","volume":"49","author":"Guttmann","year":"2016","journal-title":"J. Phys. A: Math. Theoret."},{"key":"R21","unstructured":"Massazza P., On counting k-convex polyominoes, in Proceedings of the 23rd Italian Conference on Theoretical Computer Science, ICTCS 2022, Rome, Italy, September 7-9, 2022. Vol. 3284 of CEUR Workshop Proceedings, edited by Lago U.D. and Gorla D.. CEUR-WS.org (2022) 116\u2013121."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2024009\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T09:12:03Z","timestamp":1711444323000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2024009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":21,"alternative-id":["ita220046"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2024009","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]}}}