Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem

Paweł Żyliński

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

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.

Détail

DOI : 10.37236/1046

Classification : 05C15, 05C90
Mots-clés : orthogonal polygon, quadrilateralization, vertex guards, dual graph