TY - JOUR

T1 - Tiling with Squares and Packing Dominos in Polynomial Time

AU - Aamand, Anders

AU - Abrahamsen, Mikkel

AU - Rasmussen, Peter M.R.

AU - Ahle, Thomas D.

N1 - Publisher Copyright: © 2023 Copyright held by the owner/author(s).

PY - 2023

Y1 - 2023

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 [6]. 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 and , 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 [6]. 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 and , respectively.

KW - Packing

KW - polyominos

KW - tiling

U2 - 10.1145/3597932

DO - 10.1145/3597932

M3 - Journal article

AN - SCOPUS:85166390685

VL - 19

SP - 1

EP - 28

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 3

M1 - 30

ER -