Art gallery problem
From Wikipedia, the free encyclopedia
The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards which together can observe the whole gallery. In the computational geometry version of the problem the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set S of points is said to guard a polygon if, for every point p in the polygon, there is some 
such that the line segment between p and q does not leave the polygon.
Contents |
[edit] Two dimensions
The art gallery problem was originally posed by Victor Klee in 1973.
There are numerous variations of the original problem that are also referred to as the art gallery problem. In some versions guards are restricted to the perimeter, or even to the vertices of the polygon. Some versions require only the perimeter or a subset of the perimeter to be guarded.
Solving the version in which guards must be placed on vertices and only vertices need to be guarded is equivalent to solving the dominating set problem on the visibility graph of the polygon.
[edit] Chvátal's art gallery theorem
Chvátal's art gallery theorem, named after Václav Chvátal,[1] gives an upper bound on the minimal number of guards. It states that 
guards are always sufficient and sometimes necessary to guard a simple polygon with n vertices.
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.[2]
[edit] Generalizations
Chvátal's estimate remains valid if the restriction to guards at corners is loosened to guards at any point not exterior to the polygon.
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 only 
guards are needed. 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"): 
are sometimes necessary and always sufficient. In other words, the infinite exterior is more challenging to cover than the finite interior.
[edit] Computational complexity
The decision problem versions of the art gallery problem and all of its standard variations are NP-complete, as proven by Aggarwal[3] and Lee and Lin[4]. Regarding approximation algorithms, Eidenbenz et al.[5] proved that the problem is APX-hard. An interesting open problem regarding the art gallery problem is whether or not it is actually in APX.
Kooshesh and Moret[6] gave a linear time algorithm for guarding a simple polygon with at most vertex guards.
[edit] Three dimensions
If a museum is represented in three dimensions as a polyhedron, then putting a guard at each vertex will not ensure that all of the museum is under observation. Although all of the surface of the polyhedron would be surveyed, for some polyhedra there are points in the interior which might not be under surveillance.
[edit] See also
[edit] Notes
- ^ Chvátal, V. (1975), "A combinatorial theorem in plane geometry", Journal of Combinatorial Theory, Series B 18: 39–41, doi:.
- ^ Fisk, S., A short proof of Chvátal's watchman theorem, J. Combin. Theory Ser. B 24 (1978), no. 3, 374.
- ^ A. Aggarwal. The art gallery problem: Its variations, applications, and algorithmic aspects. PhD thesis, Johns Hopkins University, 1984.
- ^ D. T. Lee and A. K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32:276-282, 1986.
- ^ S. Eidenbenz, C. Stamm, and P. Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79-113, 2001.
- ^ A. A. Kooshesh and B. M. E. Moret. Three-coloring the vertices of a triangulated simple polygon. Pattern Recognition, 25, 1992.
[edit] Further reading
- O'Rourke, Joseph (1987). Art Gallery Theorems and Algorithms. Oxford University Press. ISBN 0-19-503965-3. http://maven.smith.edu/~orourke/books/ArtGalleryTheorems/art.html.
- Shermer, Thomas (1992). "Recent Results in Art Galleries". Proceedings of the IEEE 80 (9): 1384–1399. doi:.
