{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T13:13:26Z","timestamp":1768482806341,"version":"3.49.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Independent Research Fund Denmark","award":["0164-00022B"],"award-info":[{"award-number":["0164-00022B"]}]},{"DOI":"10.13039\/100008398","name":"VILLUM Foundation","doi-asserted-by":"crossref","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Independent Research Fund Denmark","award":["1054-00032B"],"award-info":[{"award-number":["1054-00032B"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"\n A polyomino is a polygonal region with axis-parallel edges and corners of integral coordinates, which may have holes. In this paper, we consider planar tiling and packing problems with polyomino pieces and a polyomino container\n P<\/jats:italic>\n . We give polynomial-time algorithms for deciding if\n P<\/jats:italic>\n can be tiled with\n k<\/jats:italic>\n \u00d7\n k<\/jats:italic>\n squares for any fixed\n k<\/jats:italic>\n which can be part of the input (that is, deciding if\n P<\/jats:italic>\n is the union of a set of non-overlapping\n k \u00d7 k<\/jats:italic>\n squares) and for packing\n P<\/jats:italic>\n with a maximum number of non-overlapping and axis-parallel\n 2 \u00d7 1<\/jats:italic>\n dominos, allowing rotations by 90\u00b0. As packing is more general than tiling, the latter algorithm can also be used to decide if\n P<\/jats:italic>\n can be tiled by 2 \u00d7 1 dominos.\n <\/jats:p>\n \n These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2 \u00d7 2 squares is known to be NP-hard\u00a0[\n 6<\/jats:xref>\n ]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the\n area<\/jats:italic>\n or\n perimeter<\/jats:italic>\n of\n P<\/jats:italic>\n . However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial-time algorithms for the problems. Concretely, we give a simple\n O(n<\/jats:italic>\n log\n n<\/jats:italic>\n )-time algorithm for tiling with squares, where\n n<\/jats:italic>\n is the number of corners of\n P<\/jats:italic>\n . We then give a more involved algorithm that reduces the problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 3<\/jats:sup>\n ) vertices. This leads to algorithms with running times\n \n \\(O(n^3 \\frac{\\log ^3 n}{\\log ^2\\log n})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(O(n^3 \\frac{\\log ^2 n}{\\log \\log n})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , respectively.\n <\/jats:p>","DOI":"10.1145\/3597932","type":"journal-article","created":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T11:59:43Z","timestamp":1684843183000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Tiling with Squares and Packing Dominos in Polynomial Time"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0402-0514","authenticated-orcid":false,"given":"Anders","family":"Aamand","sequence":"first","affiliation":[{"name":"Computer Science and Artificial Intelligence Lab, MIT, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2734-4690","authenticated-orcid":false,"given":"Mikkel","family":"Abrahamsen","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9747-0479","authenticated-orcid":false,"given":"Thomas D.","family":"Ahle","sequence":"additional","affiliation":[{"name":"Meta, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9219-8410","authenticated-orcid":false,"given":"Peter M. R.","family":"Rasmussen","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0022-x"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574705"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)00015-N"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.9.842"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/0066"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90001-U"},{"key":"e_1_3_2_8_2","unstructured":"Francine Berman Frank Thomson Leighton and Lawrence Snyder. 1982. Optimal Tile Salvage. Technical report Purdue University Department of Computer Sciences https:\/\/docs.lib.purdue.edu\/cgi\/viewcontent.cgi?article=1321&context=cstech."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1042929"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/66.920727"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(90)90057-4"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSM.2004.836656"},{"key":"e_1_3_2_14_2","first-page":"33","volume-title":"Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG\u201909)","author":"El-Khechen Dania","year":"2009","unstructured":"Dania El-Khechen, Muriel Dulieu, John Iacono, and Nikolaj Van Omme. 2009. Packing \\(2\\times 2\\) unit squares into grid polygons is NP-complete. In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG\u201909). 33\u201336. http:\/\/cccg.ca\/proceedings\/2009\/cccg09_09.pdf."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_3_2_16_2","volume-title":"Puzzle-math","author":"Gamow George","year":"1958","unstructured":"George Gamow and Marvin Stern. 1958. Puzzle-math. Macmillan."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.61"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1954.11988548"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(94)90042-6"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9884-9"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSM.2019.2945482"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267790"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.2312\/egsh.20101036"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSM.2007.896636"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789162997"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15781-3_18"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9807-1"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.06.008"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000626"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1173-3"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1990.11995660"},{"key":"e_1_3_2_34_2","volume-title":"Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10\u201312, 2011","author":"Renssen Andr\u00e9 van","year":"2011","unstructured":"Andr\u00e9 van Renssen and Bettina Speckmann. 2011. The 2x2 simple packing problem. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10\u201312, 2011. http:\/\/www.cccg.ca\/proceedings\/2011\/papers\/paper14.pdf."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80007-8"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597932","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3597932","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:59Z","timestamp":1750178279000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597932"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,14]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3597932"],"URL":"https:\/\/doi.org\/10.1145\/3597932","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,14]]},"assertion":[{"value":"2022-04-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}