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 in unit squares. We study the combinatorics of guarding polyominoes in terms of the parameter in, in contrast with the traditional parameter n, the number of vertices of P; in particular, we show that left perpendicularm+1/3right perpendicular point guards are always sufficient and sometimes necessary to cover an m-polyomino. When m <= 4, the point guard sufficiency condition yields a strictly lower guard number than left perpendicularn/4right perpendicular, given by the art gallery theorem for orthogonal polygons. When pixels behave themselves like guards (pixel guards), we prove that left perpendicular3m/11right perpendicular + 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 NP-hard. We provide polynomial-time algorithms to solve exactly some special cases in which the polyornino is "thin".