Art gallery theorem

From Wikipedia, the free encyclopedia

The art gallery theorem (sometimes called Chvátal's art gallery theorem, after Václav Chvátal) states that in an art gallery with $n$ different corners, there needs to be at most $\lfloor n/3 \rfloor$ (see floor function) watchmen positioned in the corners to watch over the entire gallery. More specifically

Given a simple polygon on $n$ vertices, the number of people posted at the vertices needed to view every point in it is $\lfloor n/3 \rfloor$

The result is the same if the restriction to guards at corners is loosened to guards at any point not exterior to the polygon. The question about how many vertices/watchmen were needed was posed to Chvátal by Victor Klee in 1973. Chvátal proved it shortly thereafter. Chvátal's proof was later simplified by Steve Fisk, via a 3-coloring argument.

The problem of finding the minimum number of guards required for a specific art gallery is known as the art gallery problem, and is NP-hard.

There are a number of generalizations and specializations of the original art-gallery theorem. One of the cleanest specializes to orthogonal polygons, those whose edges/walls meet at right angles. For these polygons, rather than $\lfloor n/3 \rfloor$ , only $\lfloor n/4 \rfloor$ guards are needed. Thus, for n=100, only 25 rather than 33 guards are needed to guard the interior. (There are at least three distinct proofs of this result, none of them simple: by Kahn, Klawe, and Kleitman; by Lubiw; and by Sack.)

A related problem asks for the number of guards to cover the exterior of an arbitrary polygon (the "Fortress Problem"): $\lceil n/2 \rceil$ are sometimes necessary and always sufficient. So the infinite exterior is more challenging to cover than the finite interior: a 100-vertex fortress might need 50 guards.