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 
(see floor function) watchmen positioned in the corners to watch over the entire gallery. More specifically
Given a simple polygon, the number of people posted at the vertices needed to view every point in it is
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. This specific problem has been proven intractable, i.e., NP-Complete.
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 , only 
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.) Another related problem asks for the number of guards to cover the exterior of an abribrary polygon (the "Fortress Problem"): 
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.
[edit] External links
[edit] References
The results mentioned in this article are proved in
- O'Rourke, Joseph (1987). Art Gallery Theorems and Algorithms. Oxford University Press. ISBN 0-19-503965-3.
See also
- Shermer, Thomas (1992). "Recent Results in Art Galleries". Proceedings of the IEEE 80: 1384-1399.
 |
This geometry-related article is a stub. You can help Wikipedia by expanding it. |
