Chvátal watchman theorem
The following question was posed by V. Klee: How many guards are necessary (and sufficient) to guard (visually cover) a polygonal room (an art gallery) of $n$ vertices?
The question was answered by V. Chvátal [a1]. He proved that $\lfloor n/3\rfloor$ guards are sometimes necessary and always sufficient to guard a polygonal room of $n$ vertices.
|[a1]||V. Chvátal, "A combinatorial theorem in plane geometry" J. Combin. Th. B , 18 (1975) pp. 39–41|
|[a2]||S. Fisk, "A short proof of Chvátal's watchman theorem" J. Combin. Th. B , 24 (1978) pp. 374|
Chvátal theorem. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Chv%C3%A1tal_theorem&oldid=33152