TOPICS

# Art Gallery Theorem

Also called Chvátal's art gallery theorem. If the walls of an art gallery are made up of straight line segments, then the entire gallery can always be supervised by watchmen placed in corners, where is the floor function. This theorem was proved by Chvátal (1975). It was conjectured that an art gallery with walls and holes requires watchmen, which has now been proven by Bjorling-Sachs and Souvaine (1991, 1995) and Hoffman et al. (1991).

In the Season 2 episode "Obsession" (2006) of the television crime drama NUMB3RS, Charlie mentions the art gallery theorem while building an architectural model.

Illumination Problem, Triangulation, Voronoi Diagram

## Explore with Wolfram|Alpha

More things to try:

## References

Bjorling-Sachs, I. and Souvaine, D. L. "A Tight Bound for Guarding Polygons with Holes." Report LCSR-TR-165. New Brunswick, NJ: Lab. Comput. Sci. Res., Rutgers Univ., 1991.Bjorling-Sachs, I. and Souvaine, D. L. "An Efficient Algorithm for Guard Placement in Polygons with Holes." Disc. Comput. Geom. 13, 77-109, 1995.Chvátal, V. "A Combinatorial Theorem in Plane Geometry." J. Combin. Th. 18, 39-41, 1975.de Berg, M.; van Kreveld, M.; Overmars, M.; and Schwarzkopf, O. Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin: Springer-Verlag, pp. 48 and 59, 2000.DIMACS Research and Education Institute. "Art Gallery Problems." http://dimacs.rutgers.edu/~cristofa/Xfiles/art.htmlFisk, S. "A Short Proof of Chvátal's Watchman Theorem." J. Combin. Th. Ser. B 24, 374, 1978.Fournier, A. and Montuno, D. Y. "Triangulating Simple Polygons and Equivalent Problems." ACM Trans. Graphics 3, 153-174, 1984.Garey, M. R.; Johnson, D. S.; Preparata, F. P.; and Tarjan, R. E. "Triangulating a Simple Polygon." Inform. Process. Lett. 7, 175-179, 1978.Hoffmann, F.; Kaufmann, M.; and Kriegel, K. "The Art Gallery Theorem for Polygons with Holes." Proc. 32nd Annual IEEE Sympos. Found. Comput. Sci., 39-48, 1991.Honsberger, R. "Chvátal's Art Gallery Theorem." Ch. 11 in Mathematical Gems II. Washington, DC: Math. Assoc. Amer., pp. 104-110, 1976.Kahn, J.; Klawe, M.; and Kleitman, D. "Traditional Galleries Require Fewer Watchmen." SIAM J. Alg. Disc. Math. 4, 194-206, 1993.Klee, V. "On the Complexity of -Dimensional Voronoi Diagrams." Archiv. Math. 34, 75-80, 1980.O'Rourke, J. Art Gallery Theorems and Algorithms. New York: Oxford University Press, 1987.O'Rourke, J. §2.3 in Computational Geometry in C, 2nd ed. Cambridge, England: Cambridge University Press, 1998.Stewart, I. "How Many Guards in the Gallery?" Sci. Amer. 270, 118-120, May 1994.Tucker, A. "The Art Gallery Problem." Math Horizons 1, 24-26, Spring 1994.Urrutia, J. "Art Gallery and Illumination Problems." Ch. 22 in Handbook of Computational Geometry (Ed. J.-R. Sack and J. Urrutia). Amsterdam, Netherlands: North-Holland, pp. 973-1027, 2000.Wagon, S. "The Art Gallery Theorem." §10.3 in Mathematica in Action. New York: W. H. Freeman, pp. 333-345, 1991.Wells, D. The Penguin Dictionary of Curious and Interesting Geometry. London: Penguin, p. 9, 1991.

## Referenced on Wolfram|Alpha

Art Gallery Theorem

## Cite this as:

Weisstein, Eric W. "Art Gallery Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ArtGalleryTheorem.html