GUARDING A POLYGON FROM TWO NEARLY-OPPOSITE DIRECTIONS.

In this paper, we study a variant of the classical art-gallery problem, in which we require that each point of the art gallery is observed by two guards from nearly-opposite directions, ideally from front and back. We call a polygon P α-guarded by a set G of guards if every point p in P is visible from two guards g1,g2 in G satisfying α ≤ ∠g1pg2 ≤ π. We show that any simple n-gon is ⅔π-guarded by its n vertex guards, and there are simple n-gons that require at least n guards. Any simple n-gon can be (π – δ)-guarded by $\left( {\frac{{4\pi }}{\delta }\, + \,1} \right)n$ guards, and there are simple n-gons that require at least $\frac{\pi}{{4\delta}}\,(n\, - \,1)$ guards in any guard placement. We prove that the region of a simple n-gon that is α-guarded by k guards can have Θ(nk + k4) complexity in the worst case. Given simple n-gon P and k guard positions, we can decide for a fixed 0 < α < π whether P is α-guarded in O((nk2 + k4) log2 nk) time and find the largest α < π for which P is α-guarded in O((nk2 + k4) log6 nk) time. [ABSTRACT FROM AUTHOR]