  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\times 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\times k$
squares) and one for packing $P$ with a maximum number of non-overlapping and
axis-parallel $2\times 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 $2\times 1$ dominos.
  These are classical problems with important applications in VLSI design, and
the related problem of finding a maximum packing of $2\times 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(n\log 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$.
