The art gallery theorem, revisited

The art gallery theorem asserts that any polygon with n vertices can be protected by at most [n/3] stationary guards. The original proof by Chvátal uses a nonroutine and nonintuitive induction. We give a simple inductive proof of a new, more general result, the constrained art gallery theorem: If V∗and E∗are specified sets of vertices and edges that must contain guards, then the polygon can be protected by at most [(n + 2|V∗| + |E∗|) /3] guards. Our result reduces to Chvátal's art gallery theorem when V∗and E∗are empty. We give a second short proof of this generalization in the spirit of Fisk's proof of the art gallery theorem using graph colorings. © THE MATHEMATICAL ASSOCIATION OF AMERICA.