# Tiling with Squares and Packing Dominos in Polynomial Time

arXiv: https://arxiv.org/abs/2011.10983 · HTML: https://mlsanity.com/paper/2011.10983/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2020.

## Built on by (most cited first, 2 of 2)

- [Domino Denoise: An Accurate Blind Zero-Shot Denoiser using Domino Tilings](https://mlsanity.com/paper/2212.02439/) (2022)
- [On the Exact Algorithmic Extraction of Finite Tesselations Through Prime Extraction of Minimal Representative Forms](https://mlsanity.com/paper/2603.00911/) (2026)

## Abstract (arXiv)

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^circ. 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(nlog n) algorithm for tiling with squares, and a more involved O(n3,polylog, n) algorithm for packing and tiling with dominos, where n is the number of corners of P.