{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T00:29:51Z","timestamp":1724891391847},"reference-count":15,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T00:00:00Z","timestamp":1724803200000},"content-version":"vor","delay-in-days":240,"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,7,11]]},"published-print":{"date-parts":[[2024]]},"abstract":"<jats:p>This paper addresses a generalization of polyominoes called (<jats:italic>a<\/jats:italic>, <jats:italic>b<\/jats:italic>)-<jats:italic>connected discrete figures<\/jats:italic>, where <jats:italic>a<\/jats:italic> and <jats:italic>b<\/jats:italic> represent the connectivity of the foreground (<jats:italic>i.e. black pixels<\/jats:italic>) and background (<jats:italic>i.e. white pixels<\/jats:italic>), respectively. Formally, a finite set of pixels <jats:italic>P<\/jats:italic> is (<jats:italic>a<\/jats:italic>, <jats:italic>b<\/jats:italic>)-connected if <jats:italic>P<\/jats:italic> is <jats:italic>a<\/jats:italic>-connected and <jats:italic>P<\/jats:italic> is <jats:italic>b<\/jats:italic>-connected. By adapting a combinatorial structure enumeration algorithm by J. L. Martin and employing breadth-first search ordering on the pixels of the figures, we sequentially generate all (<jats:italic>a<\/jats:italic>, <jats:italic>b<\/jats:italic>)-connected discrete figures up to size <jats:italic>n<\/jats:italic> = 18, utilizing minimal storage space. This paper presents an extended version of the research presented at the 2022 GASCom conference.<\/jats:p>","DOI":"10.1051\/ita\/2024013","type":"journal-article","created":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T08:00:18Z","timestamp":1724832018000},"page":"16","source":"Crossref","is-referenced-by-count":0,"title":["On the generation of discrete figures with connectivity constraints"],"prefix":"10.1051","volume":"58","author":[{"given":"Hugo","family":"Tremblay","sequence":"first","affiliation":[]},{"given":"Julien","family":"Vernay","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,8,28]]},"reference":[{"key":"R1","unstructured":"Golomb S.W., Polyominoes. Charles Scribners\u2019 Sons (1965)."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Sunada T., Topological Crystallography. Springer (2013).","DOI":"10.1007\/978-4-431-54177-6"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Kobilarov M., Desbrun M., Marsden J. and Sukhatme G., A discrete geometric optimal control framework for systems with Symmetries, in Proceedings of Robotics: Science and Systems, Atlanta, GA, USA (2007).","DOI":"10.15607\/RSS.2007.III.021"},{"key":"R4","doi-asserted-by":"crossref","first-page":"1711","DOI":"10.1007\/s00034-014-9913-3","volume":"34","author":"Du","year":"2015","journal-title":"Circuits Syst. Signal Process."},{"key":"R5","doi-asserted-by":"crossref","first-page":"L155","DOI":"10.1088\/0305-4470\/19\/3\/011","volume":"19","author":"Lam","year":"1986","journal-title":"J. Phys. A: Math. Gen."},{"key":"R6","unstructured":"Martin J.L., Phase Transitions and Critical Phenomena, Vol. 97. Academic Press, London and New York (1974) 97\u2013112."},{"key":"R7","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/BF01020788","volume":"29","author":"Redner","year":"1982","journal-title":"J. Stat. Phys."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Golomb S.W., Polyominoes: Puzzles, Patterns, Problems, and Packings. Princeton University Press (1994).","DOI":"10.1515\/9780691215051"},{"key":"R9","doi-asserted-by":"crossref","first-page":"4867","DOI":"10.1088\/0305-4470\/32\/26\/305","volume":"32","author":"Jensen","year":"1999","journal-title":"J. Phys. A: Math. Gen."},{"key":"R10","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1016\/j.cviu.2007.06.003","volume":"113","author":"Bose","year":"2009","journal-title":"Comput. Vis. Image Understand."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Massazza P., Hole-free partially directed animals, in Developments in Language Theory, edited by Hofman P. and Skrzypczak M.. Springer International Publishing, Cham (2019) 221\u2013233.","DOI":"10.1007\/978-3-030-24886-4_16"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Dorigatti V. and Massazza P., Partially directed animals with a bounded number of holes, in Language and Automata Theory and Applications, edited by Leporati A., Mart\u00edn-Vide C., Shapira D. and Zandron C.. Springer International Publishing, Cham (2021) 16\u201328.","DOI":"10.1007\/978-3-030-68195-1_2"},{"key":"R13","unstructured":"Vernay J., Github repository: discrete-figures (2023)."},{"key":"R14","unstructured":"Shoshany B., A c++17 thread pool for high-performance scientific computing. (2021)."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Flajolet P. and Sedgewick R., Analytic Combinatorics, 1st edn. Cambridge University Press, USA (2009).","DOI":"10.1017\/CBO9780511801655"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2024013\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T08:00:33Z","timestamp":1724832033000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2024013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":15,"alternative-id":["ita220052"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2024013","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]}}}