How to Guard an Art Gallery and Other Discrete Mathematical Adventures

3. How to Guard an Art Gallery

3 How to Guard an Art Gallery I found I could say things with color and shapes that I couldn’t say any other way— things I had no words for. Georgia O’Keeffe 3.1 The Sunflower Art Gallery Figure 3.1 shows the unusual floor plan of the Sunflower Art Gallery and the locations of four guards. Each guard is stationary but can rotate in place to scan the surroundings in all directions. Guards cannot see through walls or around corners. Every point in the gallery is visible to at least one guard, and theft of the artwork is prevented. Of course, it Figure 3.1: The Sunflower Art Gallery 73 74 D is c r e t e M a t he m a t ic a l A d v en t u r es would be more economical to protect the gallery with fewer guards, if possible. Question. What is the smallest number of guards required to protect the Sunflower Art Gallery? Removing any one of the four guards in Figure 3.1 leaves part of the gallery unprotected. Nonetheless, it is possible to protect the gallery with three suitably positioned guards. We can dismiss the lowest guard if we move the leftmost guard slightly downward. However, we cannot get by with two guards. To see why, consider the eight outer corners of the gallery. It is not possible for one guard anywhere in the gallery to keep an eye on more than three of these corners. So two guards could protect at most six of the eight outer corners. The Sunflower Art Gallery has 16 walls and needs three guards. This raises a broader question. Question. What is the smallest number of guards needed to protect any 16-walled gallery, regardless of its shape? Our art gallery questions involve issues in computational geometry, a large and active field that blends geometry with ideas from discrete mathematics and optimization. Applications of computational geometry include: ◦ Barcode scanners that read prices at grocery stores ◦ Digital special effects common in today’s movies and video games1 ◦ Calculations performed by global positioning satellite (GPS) receivers to determine location, speed, and direction 1 The special case of representing straight lines on a computer monitor is the topic of Chapter 4. H o w t o G u a r d a n A r t G a l l e r y 75 ◦ Algorithms executed by machines and robotic arms on assembly lines to carry out complex tasks in a specific order ◦ Computerized fingerprint recognition schemes used in security systems and forensics At the core of most problems in computational geometry is a connection between theory and algorithms. The theory describes or defines desired geometric configurations, which the algorithms construct using known mathematical procedures. Theoretical and algorithmic issues are tightly linked in art gallery problems. For instance, we will discover a theorem asserting that every w-walled art gallery can be protected by at most w/3 guards. Our demonstration of this result leads to an algorithm telling us exactly where to post the guards. We also look at several variations, including an unsolved three-dimensional guarding problem. 3.2 Art Gallery Problems Let us define our terms carefully. For our purposes, an art gallery is a polygon in the plane.2 The polygon need not serve as the floor plan of any real-world art gallery. An art gallery includes the interior region as well as the boundary segments—the walls. We let G denote an arbitrary art gallery and write Gw for an art gallery with w walls. Let p be any point in an art gallery. The point q is visible to p provided the line segment joining p and q does not exit the gallery. (We also assume that every point is visible to itself.) The segment represents the sight line of a guard. A set of guards protects an art gallery provided every point in 2 More precisely, an art gallery is a simple polygon. We exclude polygons with holes, boundaries that cross, and other oddities. 76 D is c r e t e M a t he m a t ic a l A d v en t u r es the gallery is visible to at least one guard. Note that a guard at a corner protects the two adjacent walls...