Art gallery problem

From Wikipedia, the free encyclopedia

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. The motivation for the problem is the real-world problem of guarding an art gallery with the minimum number of security cameras that can each rotate to obtain a full field of vision. In the computational geometry version of the problem the layout of the art gallery is represented by a simple polygon and each security camera 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 $q\in S$ such that the line segment between $p$ and $q$ does not leave the polygon.

1 Two dimensions
2 Three dimensions
3 See also
4 References

[edit] Two dimensions

Four cameras cover this gallery.

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.

Chvátal's art gallery theorem^[1] states that $\left\lfloor \frac{n}{3} \right\rfloor$ guards are always sufficient and sometimes necessary to guard a simple polygon with $n$ vertices. Kooshesh and Moret^[2] gave a linear time algorithm for guarding a simple polygon with at most $\left\lfloor \frac{n}{3} \right\rfloor$ vertex guards.

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.

[edit] Three dimensions

An example of a polyhedron with interior points not visible from any vertex.

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, there are points in the interior of the polyhedron which might not be under surveillance.

[edit] See also

O'Rourke, Joseph (1987). Art Gallery Theorems and Algorithms. Oxford University Press. ISBN 0-19-503965-3.

[edit] References

^ V. Chvátal. A combinatorial theorem in plane geometry. J. Comb. Theory Series B, 18:39-41, 1975.
^ A. A. Kooshesh and B. M. E. Moret. Three-coloring the vertices of a triangulated simple polygon. Pattern Recognition, 25, 1992.
^ 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.