Personal tools
You are here: Home CG seminar 2022 Tiling with Squares and Packing Dominos in Polynomial Time
« August 2022 »
Log in

Forgot your password?

Tiling with Squares and Packing Dominos in Polynomial Time

Mםonday, May 2nd, 4:10pm Tel Aviv time, Dach Hall


Mikkel Abrahamsen, University of Copenhagen


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
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 one 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 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(nlogn) algorithm for tiling with
squares, and a more involved O(n^3 polylogn) algorithm for packing and tiling
with dominos, where n is the number of corners of P.
This is a joint work with Anders Aamand, Thomas D. Ahle, and Peter M. R. Rasmussen.
Document Actions