Guarding 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. When m ≤ 3n/ 4 -4, the point guard sufficiency condition yields a strictly lower guard number than [ n /4], given by the art gallery theorem for orthogonal polygons. When pixels behave themselves like guards (pixel guards), we prove that [3m /11] + 1 guards are sufficient and sometimes necessary to cover an m-polyomino. We also study the algorithmic complexity of computing optimal guard sets for polyominoes. We prove that determining the guard number of a given m-polyomino is NPhard. We provide polynomial-time algorithms to solve exactly some special cases in which the polyomino is "thin".