Chvátal's art gallery theorem | watchman 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 ⌊n/3⌋ watchmen placed in corners, where ⌊x⌋ is the floor function. This theorem was proved by Chvátal. It was conjectured that an art gallery with n walls and h holes requires ⌊(n + h)/3⌋ watchmen, which has now been proven by Bjorling-Sachs and Souvaine (1991, 1995) and Hoffman et al. (1991). In the Season 2 episode "Obsession" of the television crime drama NUMB3RS, Charlie mentions the art gallery theorem while building an architectural model.

illumination problem | triangulation | Voronoi diagram