The Orthogonal Art Gallery Theorem with Constrained Guards

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.