Optimally Guarding 2-Reflex Orthogonal Polyhedra by Reflex Edge Guards
share
We study the problem of guarding an orthogonal polyhedron having reflex edges in just two directions (as opposed to three) by placing guards on reflex edges only. We show that (r - g)/2 + 1 reflex edge guards are sufficient, where r is the number of reflex edges in a given polyhedron and g is its genus. This bound is tight for g=0. We thereby generalize a classic planar Art Gallery theorem of O'Rourke, which states that the same upper bound holds for vertex guards in an orthogonal polygon with r reflex vertices and g holes. Then we give a similar upper bound in terms of m, the total number of edges in the polyhedron. We prove that (m - 4)/8 + g reflex edge guards are sufficient, whereas the previous best known bound was 11m/72 + g/6 - 1 edge guards (not necessarily reflex). We also discuss the setting in which guards are open (i.e., they are segments without the endpoints), proving that the same results hold even in this more challenging case. Finally, we show how to compute guard locations in O(n log n) time.
READ FULL TEXT
