The Orthogonal Art Gallery Theorem with Constrained Guards

Abstract 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.