Friday, April 29, 2011

face guards by Andrew Winslow, Diane Souvaine and me

Abstract:

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,





while for general polyhedra





Example of the orthogonal polyhedron:






PDF version of the submitted paper.

No comments: