Orthogonal Art Galleries with Holes: A Coloring Proof of Aggarwal's Theorem

Abstract

We prove that $\lfloor{n+h\over 4}\rfloor$ vertex guards are always sufficient to see the entire interior of an $n$-vertex orthogonal polygon $P$ with an arbitrary number $h$ of holes provided that there exists a quadrilateralization whose dual graph is a cactus. Our proof is based upon $4$-coloring of a quadrilateralization graph, and it is similar to that of Kahn and others for orthogonal polygons without holes. Consequently, we provide an alternate proof of Aggarwal's theorem asserting that $\lfloor{n+h\over 4}\rfloor$ vertex guards always suffice to cover any $n$-vertex orthogonal polygon with $h \le 2$ holes.