Face guards for art galleries
Diane L. Souvaine, Raoul L. Veroy, Andrew Winslow · 2011
A classic problem in computational geometry is the art gallery problem: given an enclosure, how should guards be placed to ensure every location in the enclosure is seen by some guard. In this paper we consider guarding the interior of a simple polyhedron using face guards: guards that roam over an entire interior face of the polyhedron. Bounds for the number of face guards g that are necessary and sufficient to guard any polyhedron with f faces are given. We show that for orthogonal polyhedra, ⌊f/7 ⌋ ≤ g ≤ ⌊f/6⌋, while for general polyhedra ⌊f/5 − 2/5 ⌋ ≤ g ≤ ⌊f/2⌋.