# 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

### Abstract:

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.