Full bibliography

We extend and unify most known results about guarding orthogonal polygons by introducing the same-sign diagonal graphs of a convex quadrangulation and applying results about vertex covers for graphs. Our approach also yields new theorems and often guarantees two disjoint vertex guard sets of relatively small cardinality. For instance, an orthogonal polygon on n vertices has two disjoint vertex guard sets of cardinality at most (Formula presented.). We give new proofs of Aggarwal’s one-hole theorem and the orthogonal fortress theorem. We prove that an orthogonal polygon with n vertices and any number of holes can be protected by at most (Formula presented.) vertex guards, improving the best known bound of (Formula presented.). Also, an orthogonal polygon with n vertices and h holes can be protected by (Formula presented.) guarded guards, which is best possible when (Formula presented.). Moreover, for orthogonal fortresses with n vertices, (Formula presented.) guarded guards are always sufficient and sometimes necessary. © 2016, Springer Science+Business Media New York (outside the USA).

0 citations (Crossref) [2023-10-31] Citation Key Alias: lens.org/044-855-289-331-994 tex.type: [object Object]