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 two polynomial time algorithms, one for deciding if $P$ can be tiled with $ktimes 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 $ktimes k$ squares) and one for packing $P$ with a maximum number of non-overlapping and axis-parallel $2times 1$ dominos, allowing rotations by $90^circ$. As packing is more general than tiling, the latter algorithm can also be used to decide if $P$ can be tiled by $2times 1$ dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of $2times 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 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)$ algorithm for tiling with squares, and a more involved $O(n^3,text{polylog}, n)$ algorithm for packing and tiling with dominos, where $n$ is the number of corners of $P$.
Download