Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals called the interior walls. Each interior wall has an arbitrarily placed, arbitrarily small doorway.We determine (for all m and n) the minimum number of guards that always suffices to watch all locations in an art gallery with n vertices and m interior walls. We also solve the case when all rooms are convex with minimum size at least r.
The proofs yield linear time algorithms for guard placement in most cases.