Art Gallery Theorem

Also called Chvátal's art gallery theorem. If the walls of an art gallery are made up of n straight line segments, then the entire gallery can always be supervised by |_n/3_| watchmen placed in corners, where |_x_| is the floor function. This theorem was proved by Chvátal (1975). It was conjectured that an art gallery with n walls and h holes requires |_(n+h)/3_| 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.

See also

Illumination Problem, Triangulation, Voronoi Diagram

Explore with Wolfram|Alpha


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, 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.", 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 d-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.

Subject classifications