The Art Gallery Theorem

We will discuss how to place guards in corners (vertices) of an art gallery whose form is a simple closed polygon, in such a way that together they supervise the whole gallery---every part of it can be seen by at least one guard. The question is how to place them such that the fewest number of guards is needed.

Consider the example to the right. A guard placed on the red vertex can see the red area. A guard placed at the blue vertex can see the blue area. Together they can supervise the red-blue-purple colored area. Obviously three more guards would be necessary to guard the three small yellow parts not supervised yet. Yet, as we will see later, four guards suffice in this example.

Placing the guards at the walls but not necessarily in vertices could sometimes reduce the number of guards needed further, but here we will stick to the condition that they have to be at vertices.

It is obvious that the number n of guards will always suffice---it is also a natural measure of how difficult the task may be. Trying some examples, one may observe that usually one can guard n-vertex galleries with at most n/3 guards. This was Klee's conjecture, shown by Chvatal:

Theorem [Chvatal 1973] Every art gallery formed by a closed polygonal curve with n vertices can be supervised by n/3 or fewer guards. The proof presented is due to Steve Fisk.

Step I: Divide and Conquer: We triangulate the gallery, meaning we draw noncrossing lines from vertices to vertices such that the gallery area is divided into triangles.

Why and how can this always be achieved? Select any vertex (blue) and look at its neighboring vertices (green) . If the gallery is not itself a triangle, these two green neighbors are not adjacent. Either the two green neighbors can see each other, in which case the line between them can be drawn. Or, if the two green neighbors cannot see each other , the blue vertex must see another vertex, and we can draw that edge. . After drawing the line, the gallery falls into two smaller galleries, and we can proceed as long as the resulting galleries are not triangles.

Step II: Now we color the vertices using only three colors in such a way that the vertices for each triangle have all three colors .

Why and how can this be done? We start with any triangle and color its three vertices with different colors . Then go to the triangles sharing an edge with the triangle handled before ---they also share two vertices, therefore the third vertex should be colored with the remaining color . We continue until all vertices are colored. .

Conclusion: Now every color class sees the whole gallery, since every point of the gallery lies in a triangle, which has three differently colored vertices, therefore can be seen by each color class. Since the number of blue vertices plus the number of green vertices plus the number of yellow vertices equals n, one of these three numbers (in our example the number of green vertices) must be smaller or equal to n/3. We place the guards on the vertices of that color .

Note that this result doesn't answer all questions one might have about guarding art galleries. Even though we know that we always need at most n/3 guards, for some galleries we need less, but the procedure above does not give us a hint of how to find such minimal/optimal guard distributions.

Here you can find more examples.