Art galleries with interior walls

Consider an art gallery formed by a polygon on n vertices with m pairs of v ertices joined by interior diagonals, the interior walls. Each interior wal l has an arbitrarily placed, arbitrarily small doorway. We show that the mi nimum number of guards that suffice to guard all art galleries with n verti ces and m interior walls is min {[(2n - 3)/3], [(2m + n - 2)/4], [(2m + n)/ 3]}. If we restrict ourselves to galleries with convex rooms of size at lea st r, the answer improves to min{m, [(n + m)/r]}. The proofs lead to linear time guard placement algorithms in most cases.