Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem (Q819180): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:17, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem |
scientific article |
Statements
Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem (English)
0 references
22 March 2006
0 references
Summary: We prove that \(\left\lfloor{n+h\over 4}\right\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 \textit{J. Kahn} and others [SIAM J. Algebraic Discrete Methods 4, 194--206 (1983; Zbl 0533.05021)] for orthogonal polygons without holes. Consequently, we provide an alternate proof of Aggarwal's theorem asserting that \(\left\lfloor{n+h\over 4}\right\rfloor\) vertex guards always suffice to cover any \(n\)-vertex orthogonal polygon with \(h \leq 2\) holes.
0 references
orthogonal polygon
0 references
quadrilateralization
0 references
vertex guards
0 references
dual graph
0 references