Minimum boundary touching tilings of polyominoes

摘要

We study the problem of tiling a polyomino P with as few squares as possible such that every square in the tiling has a non-empty intersection with the boundary of P . Our main result is an algorithm which given a simply connected polyomino P computes such a tiling of P . We indicate how one can improve the running time of this algorithm for the more restricted row-column-convex polyominoes. Finally we show that a related decision problem is in NP for rectangular polyominoes.