The orthogonal art gallery theorem with constrained guards - Michael, T S; Pinciu, Val (Electronic Notes in Discrete Mathematics, 2016)
Let P be an orthogonal polygon with n vertices, and let V⁎ and E⁎ be specified sets of vertices and edges of P. We prove that P has a guard set of cardinality at most ⌊(n+3|V⁎|+2|E⁎|)/4⌋ that includes each vertex in V⁎ and at least one point of each edge in E⁎. Our bound is sharp and reduces to the orthogonal art gallery theorem of Kahn, Klawe and Kleitman when V⁎ and E⁎ are empty. © 2016 Elsevier B.V.
0 citations (Crossref) [2023-10-31] Citation Key Alias: lens.org/018-020-908-114-676 tex.type: [object Object]
Keywords: art gallery theorem; dept.mat; graph coloring; orthogonal polygon; polygon visibility

How to guard orthogonal polygons: diagonal graphs and vertex covers - Michael, T S; Pinciu, Val (Discrete and Computational Geometry, 2016)
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]
Keywords: Art gallery theorem; Orthogonal polygon; Vertex cover; Visibility; dept.mat

Multiply guarded guards in orthogonal art galleries - Michael, T S; Pinciu, Val (International Conference on Computational Science, 2001)
We prove a new theorem for orthogonal art galleries in which the guards must guard one another in addition to guarding the polygonal gallery. A set of points G in a polygon Pn is a k-guarded guard set for Pn provided that (i) for every point x in Pn there exists a point w in G such that x is visible from w; and (ii) every point in G is visible from at least k other points in G: The polygon Pn is orthogonal provided each interior angle is 90° or 270°. We prove that for k ≥ 1 and n ≥ 6 every orthogonal polygon with n sides has a k-guarded guard set of cardinality (Formula Presented.) this bound is best possible. This result extends our recent theorem that treats the case k = 1. © Springer-Verlag Berlin Heidelberg 2001.
2 citations (Crossref) [2023-10-31] tex.type: Proceedings paper
Keywords: Art gallery; Cardinalities; Computation theory; Geometry; dept.mat