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
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,
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. B24, 374, 1978.Fournier, A. and Montuno, D. Y.
"Triangulating Simple Polygons and Equivalent Problems." ACM Trans.
Graphics3, 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,
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 Horizons1,
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,
Penguin Dictionary of Curious and Interesting Geometry. London: Penguin,
p. 9, 1991.