Art Gallery Theorem

Also called Chvátal's Art Gallery Theorem. If the walls of an art gallery are made up of $n$ straight Line Segments, then the entire gallery can always be supervised by $\left\lfloor{n/3}\right\rfloor$ watchmen placed in corners, where $\left\lfloor{x}\right\rfloor$ is the Floor Function. This theorem was proved by V. Chvátal in 1973. It is conjectured that an art gallery with $n$ walls and $h$ Holes requires $\left\lfloor{(n+h)/3}\right\rfloor$ watchmen.

See also Illumination Problem

References

Honsberger, R. ``Chvátal's Art Gallery Theorem.'' Ch. 11 in Mathematical Gems II. Washington, DC: Math. Assoc. Amer., pp. 104-110, 1976.

O'Rourke, J. Art Gallery Theorems and Algorithms. New York: Oxford University Press, 1987.

Stewart, I. ``How Many Guards in the Gallery?'' Sci. Amer. 270, 118-120, May 1994.

Tucker, A. ``The Art Gallery Problem.'' Math Horizons, pp. 24-26, Spring 1994.

Wagon, S. ``The Art Gallery Theorem.'' §10.3 in Mathematica in Action. New York: W. H. Freeman, pp. 333-345, 1991.