Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem
The electronic journal of combinatorics, Tome 13 (2006)
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.
DOI :
10.37236/1046
Classification :
05C15, 05C90
Mots-clés : orthogonal polygon, quadrilateralization, vertex guards, dual graph
Mots-clés : orthogonal polygon, quadrilateralization, vertex guards, dual graph
@article{10_37236_1046,
author = {Pawe{\l} \.Zyli\'nski},
title = {Orthogonal art galleries with holes: a coloring proof of {Aggarwal's} theorem},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1046},
zbl = {1087.05020},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1046/}
}
Paweł Żyliński. Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1046
Cité par Sources :