The Art Gallery Theorem for Polyominoes

We explore the art gallery problem for the special case that the domain (gallery) P is an m-polyomino, a polyform whose cells are m unit squares. We study the combinatorics of guarding polyominoes in terms of the parameter m, in contrast with the traditional parameter n, the number of vertices of P. In particular, we show that ⌊m+1/3⌋ point guards are always sufficient and sometimes necessary to cover an m-polyomino, possibly with holes. When m < 3n/4-4, the sufficiency condition yields a strictly lower guard number than ⌊ n/4⌋, given by the art gallery theorem for orthogonal polygons. © 2012 Springer Science+Business Media, LLC.