Minimum boundary touching tilings of polyominoes
Andreas Spillner · Mathematical logic quarterly · 2005
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. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)