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.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,
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 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,
D. The
Penguin Dictionary of Curious and Interesting Geometry. London: Penguin,
p. 9, 1991.
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).
-Dimensional
Voronoi Diagrams." Archiv. Math. 34, 75-80, 1980.O'Rourke,
J.