How many guards does it take to watch an entire art gallery?
An eccentric art gallery is shaped like a simple polygon with n straight walls, and its guards can each see in every direction but never through a wall. What is the smallest number of guards — positioned anywhere inside, including at corners — that's always enough to keep every point of the gallery in someone's view, no matter how oddly the room is shaped? Victor Klee posed the question in 1973.
Reveal the answer
⌊n/3⌋ guards are always enough, and sometimes necessary — a 'comb-shaped' gallery with jagged prongs can require that many. Václav Chvátal proved the bound in 1975 by induction; Steve Fisk gave a shorter, elegant proof in 1978 by triangulating the polygon and 3-coloring its vertices, then posting guards at whichever color class is smallest. The result founded a whole branch of computational geometry, now applied to robot sensor placement and camera coverage.