2026-08-16T20:54:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16009 2024-03-06T10:56:43Z ddc:004 open_access

Tiling with Squares and Packing Dominos in Polynomial Time Aamand, Anders Abrahamsen, Mikkel Ahle, Thomas Rasmussen, Peter M. R. packing tiling polyominos 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 P. We give polynomial-time algorithms for deciding if P can be tiled with k× k squares for any fixed k which can be part of the input (that is, deciding if P is the union of a set of non-overlapping k× k squares) and for packing P with a maximum number of non-overlapping and axis-parallel 2× 1 dominos, allowing rotations by 90^∘. As packing is more general than tiling, the latter algorithm can also be used to decide if P can be tiled by 2× 1 dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2× 2 squares is known to be NP-hard [J. Algorithms 1990]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the area or perimeter of P. 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 O(nlog n)-time algorithm for tiling with squares, where n is the number of corners of P. 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 O(n³) vertices. This leads to algorithms with running times O(n³(log³ n)/(log²log n)) and O(n³(log² n)/(log log n)), respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anders Aamand and Mikkel Abrahamsen and Thomas Ahle and Peter M. R. Rasmussen 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.1 urn:nbn:de:0030-drops-160096 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.1 eng https://creativecommons.org/licenses/by/4.0/legalcode