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.
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.html
Fisk, 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.
Weisstein, Eric W. "Art Gallery Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
Contact the MathWorld Team
polygons