Tiling with Squares and Packing Dominos in Polynomial Time
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Tiling with Squares and Packing Dominos in Polynomial Time. / Aamand, Anders; Abrahamsen, Mikkel; Ahle, Thomas; Rasmussen, Peter M.R.
38th International Symposium on Computational Geometry, SoCG 2022. ed. / Xavier Goaoc; Michael Kerber. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 1 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 224).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Tiling with Squares and Packing Dominos in Polynomial Time
AU - Aamand, Anders
AU - Abrahamsen, Mikkel
AU - Ahle, Thomas
AU - Rasmussen, Peter M.R.
N1 - Publisher Copyright: © Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen; licensed under Creative Commons License CC-BY 4.0
PY - 2022
Y1 - 2022
N2 - 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(n log 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(n3) vertices. This leads to algorithms with running times O(n3loglog2 log3 nn ) and O(n3logloglog2 nn ), respectively.
AB - 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(n log 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(n3) vertices. This leads to algorithms with running times O(n3loglog2 log3 nn ) and O(n3logloglog2 nn ), respectively.
KW - packing
KW - polyominos
KW - tiling
U2 - 10.4230/LIPIcs.SoCG.2022.1
DO - 10.4230/LIPIcs.SoCG.2022.1
M3 - Article in proceedings
AN - SCOPUS:85134355587
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 38th International Symposium on Computational Geometry, SoCG 2022
A2 - Goaoc, Xavier
A2 - Kerber, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 38th International Symposium on Computational Geometry, SoCG 2022
Y2 - 7 June 2022 through 10 June 2022
ER -
ID: 342673664