You are here

Guards, Galleries, Fortresses, and the Octoplex

by T. S. Michael (U. S. Naval Academy)

Award: George Pólya

Year of Award: 2012

Publication Information: College Mathematics Journal, vol. 42, no. 3, March 2011, pp.191-200.

Summary (From the MathFest2012 Prizes and Awards Booklet)

Beginning with Victor Klee's 1973 art gallery problem—to determine the maximum number of guards needed to protect an art gallery with a simple, closed polygonal floor plan—the author offers a survey of art-gallery-type results and open problems.

After describing the fundamental problem, the author gives a visual proof, due to Steve Fisk, that a closed polygonal art gallery with \(n\) walls requires at most \([n/3]\) guards. Next he considers the more subtle question of right-angled galleries (i.e., where adjacent walls meet orthogonally), for which the corresponding maximum number of guards is \([n/4]\). Then onto fortresses, where the guards are posted outside the perimeter of the polygonal structure and the object is to protect the exterior and an inversion argument is needed. Ultimately the author explores the three-dimensional analogue of Klee's original problem and produces a surprising example of a polyhedron—the "octoplex" of the title—where, unlike the two-dimensional situation, posting a guard at every vertex does not guarantee that the entire interior is protected. Indeed, relatively little is known in the three-dimensional case.

Read the Article

About the Authors (From the MathFest2012 Prizes and Awards Booklet)

T. S. Michael received his B.S. from Caltech in 1983 and his Ph.D. from Wisconsin in 1988 under the direction of Richard Brualdi. His research focuses on combinatorics, especially combinatorial problems involving matrices or geometry. He has been on the mathematics faculty at the U.S. Naval Academy since 1990, where he coached the Putnam team for ten years and was the founding coach of the Naval Academy triathlon team. His book, How to Guard an Art Gallery and Other Discrete Mathematical Adventures, was published in 2009.

Subject classification(s): Geometry and Topology | Plane Geometry | Solid Geometry
Publication Date: 
Wednesday, August 8, 2012