«1 Guarding an Art Gallery Imagine that you are the owner of several art galleries and that you are in the process of hiring people to guard one of ...»
Art Gallery Theorems
1 Guarding an Art Gallery
Imagine that you are the owner of several art galleries and that you are in the process of
hiring people to guard one of them. Unfortunately, with so many in your possession, you
seem to have forgotten the exact shape of this particular one. In fact, all you can remember
is that the art gallery is a polygon with n sides. Of course, guards have the capacity to turn
around a full 360◦ and can see everything in their line of sight, but being terribly unﬁt, they are unwilling to move. The question we would like to answer is the following.
What is the minimum number of guards that you need to be sure that they can watch over the entire art gallery?
This question was ﬁrst posed in 1973 by Victor Klee when asked by fellow mathematician Va˘ek Chv´tal for an interesting problem. A little more precisely, let us consider our art s a gallery to be the closed set of points bounded by a polygon. We will also need to make the somewhat unrealistic assumption that our guards are points and we will allow them to stand anywhere in the polygon, even along an edge or at a vertex. Guards are able to see a point in the art gallery as long as the line segment joining them lies in the polygon.
To get a feel for the problem, consider the comb-shaped art gallery below which has ﬁfteen sides. It is clear that at least one guard is required to stand in each of the shaded areas in order to keep an eye on each of the “prongs” of the comb. Thus, at least ﬁve guards are needed to watch over the entire art gallery, and it is a simple enough matter to verify that ﬁve are actually suﬃcient. In fact, it is not too diﬃcult to see that you can form a k-pronged comb-shaped art gallery which has 3k sides and requires k guards. Furthermore, by chipping oﬀ a corner or two, it is clear that there exist art galleries which have 3k + 1 or 3k + 2 sides and require k guards.
In short, you will need to hire at least n/3 guards to watch over your art gallery, but is it possible that you might need even more? The following theorem states that you don’t, which means that the comb-shaped art gallery actually gives a worst case scenario.
n Art Gallery Theorem: Only guards or fewer are required to watch over an art gallery with n sides.
Mathellaneous 289 2 A Proof from the Book The ﬁrst proof of the art gallery theorem was produced by Chv´tal two years after the a problem was originally posed, but in 1978, a proof from the book1 was found by Steve Fisk . His proof, which we will now present, involves three main steps and is simplicity in itself.
◦ You can always triangulate a polygon.
To triangulate a polygon is to partition it into triangles using only diagonals which join pairs of vertices. This can always be done, as long as we can ﬁnd a diagonal which joins two of the vertices and lies completely inside the polygon. For if this were true, then we could use such a diagonal to cut the polygon into two smaller polygons, and then cut those into still smaller ones, iterating the process until we are left with nothing but triangles.
To see that such a diagonal always exists, consider a guard standing at a vertex X and shining a torch towards the adjacent vertex Y. If the guard were to rotate this ray of light towards the interior of the polygon, then it must at some stage hit another vertex, which we will call Z. Now we can take one of XZ or Y Z as the desired diagonal, as long as there is no vertex of the polygon which lies inside the triangle XY Z. But no such vertices could possibly exist, otherwise the rotating ray of light would have hit one of them ﬁrst.
◦ There is a nice 3-colouring of every triangulation of a polygon.
A nice 3-colouring is a way to assign a colour (or, due to the monochromatic nature of the Gazette, a number) to each vertex of the triangulation so that every triangle has vertices with three diﬀerent colours. This is an easy task if the polygon is a triangle, so let us consider what happens when there are more than three sides. But then by the result stated above, there exists a diagonal joining two of the vertices which lies completely inside the polygon. This diagonal can now be used to partition our art gallery into two smaller ones. Notice now that if we can nicely 3-colour the two smaller art galleries, then they can be glued together, possibly after relabelling the colours in one of the pieces, to give a nice 3-colouring of the original art gallery.
1Many of you will know that the renowned twentieth century mathematician Paul Erd˝s liked to talk o about “The Book”, in which God maintains the perfect proofs for mathematical theorems. Only on very rare occasions are we mere mortals allowed to snatch a glimpse of The Book, and only the very fortunate ones at that.
290 Norman Do But can we nicely 3-colour these two smaller art galleries? Of course we can... just use the same trick to split them up into smaller and smaller pieces until we are left merely with triangles, which can obviously be nicely 3-coloured!
◦ Now place your guards at the vertices which have the minority colour.
Suppose that the colour which occurs the least number of times is red, for example, and that there are actually k red vertices. Since there are n vertices altogether and only three colours, that tells us that k ≤ n/3 and since k is an integer, we have k ≤ n/3. But what happens when we place k guards at these red vertices?
Well, by the properties of a nice 3-colouring, each triangle contains a red vertex and a guard standing there can obviously watch over every part of that triangle. So every triangle in the triangulation, and hence every point in the art gallery, is being watched by at least one guard.
3 More Art Gallery Problems
Subsequent to the solution of the art gallery problem, people began to explore variations on the art gallery theme. For example, they posed the problem for guards with constrained power, for guards with enhanced power, for art galleries with restrictions, for art galleries with holes inside, for exterior guarding of art galleries and for art galleries of higher dimension, just to name a few. The myriad of results in the area prompted Joseph O’Rourke to write the monograph Art Gallery Theorems and Algorithms , which was the deﬁnitive work on the topic at its time of publication. Presented in this section are just three of the more natural and pleasing extensions to the art gallery problem.
Orthogonal Art Galleries
Imagine now that you have suddenly remembered that your art gallery isn’t just any old random polygon with n sides, but actually satisﬁes the condition that any two walls which meet do so at right angles. This is known as an orthogonal art gallery for obvious reasons and, of course, we would like to know how many guards are required to watch over an orthogonal art gallery with n sides. This time, the example of the comb-shaped art gallery does not arise, but can be modiﬁed to give an orthogonal counterpart. Such an art gallery with k prongs requires 4k edges, so we need at least n guards. The following theorem states that this is all that we need.
Mathellaneous 291 n Orthogonal Art Gallery Theorem: Only guards or fewer are required to watch over an orthogonal art gallery with n sides.
The original proof relies on the nontrivial fact that any orthogonal polygon can be partitioned into convex quadrilaterals, whose vertices are selected from those of the polygon. Once this has been established, it is a simple matter to show the existence of a nice 4-colouring of the resulting graph. Then placing guards at the vertices of the minority colour yields the desired result.
Or suppose that you have enough money to hire ﬁt guards who don’t just stand still but patrol along a particular line segment within the art gallery. The astute reader is most likely wondering how many of these “line guards” are required, a question that is answered by the following...
Art Gallery Theorem for Line Guards: Only n line guards or fewer are required to watch over an art gallery with n sides.
Perhaps having guards walking to and fro, disturbing the patrons of your art gallery, is both unnecessary and undesirable. It may be wiser to only allow your guards to patrol along an edge of the polygon. So how many of these “edge guards” are required to watch over the art gallery? Interestingly enough, the answer is unknown, but the following is believed to be true.
Art Gallery Conjecture for Edge Guards: Only n edge guards or fewer are required to watch over an art gallery with n sides, except for a few special cases.
Three-dimensional Art Galleries
It seems a natural progression for us to move up a dimension and pose the art gallery problem for polyhedra rather than polygons. Unfortunately, very little is known about this situation.
The main obstruction to progress is the surprising fact that polygon triangulation, which was central to the proof of the art gallery theorem, does not generalize to three dimensions.
A more precise statement of this fact is the following result.
There exist polyhedra which cannot be tetrahedralized. To tetrahedralize a polyhedron is to partition it into tetrahedra whose vertices are selected from those of the original polyhedron.
The simplest example of such a polyhedron was discovered by Sch¨nhardt in 1928 and can o be constructed as follows. Consider an equilateral triangular prism, where the base triangle 292 Norman Do ABC lies directly below the upper triangle A B C. Suppose that the edges of the prism are constructed from wire and that the edges AB, BC and CA have been added with extra wire. It may be helpful to imagine that we have dipped the whole wire frame into soapy liquid and that a soap ﬁlm has formed along each of the eight triangular faces.
Now consider what happens if we slowly rotate the upper triangle. If we rotate in one direction, then the rectangular faces of the prism bend outwards along the extra edges AB, BC and CA. However, if we rotate in the other direction, then the rectangular faces of the prism bend inwards, yielding a polyhedron which is not convex. At the point when we have rotated by a full 60◦, then the three edges AB, BC and CA intersect at the centre of the ﬁgure. Sch¨nhardt’s polyhedron is obtained when the rotation is by some intermediate o value, for example 30◦. In this instance, the line segments AC, BA and CB lie outside the polyhedron. However, any tetrahedron constructed from the six vertices of Sch¨nhardt’s o polyhedron must necessarily contain one of the line segments AC, BA and CB and hence, cannot lie within its interior.
Note that for two-dimensional art galleries, placing a guard at every vertex will always suﬃce to watch over the art gallery. However, this fact only follows once we have established that every polygon can be triangulated. For then, each triangle in the triangulation is guarded by the three guards at its vertices. Unfortunately, this argument does not generalize to three-dimensional art galleries. The diﬃculties posed by the existence of polyhedra which cannot be tetrahedralized is highlighted by the following unexpected result.
There exist polyhedra such that guards placed at every vertex do not see all of the interior of the polyhedron.
4 Illuminating a Room
The following illuminating problem has a very similar ﬂavour to the results presented above.
It was brought to the attention of mathematicians in 1969 by Victor Klee , the very same person who brought you the original art gallery problem. Imagine that you are standing in a room, perhaps an art gallery, in the shape of a polygon and that each wall is a mirror. If you strike a match, is it always possible to illuminate the whole room? Of course, the light Mathellaneous 293 will propagate according to the well-known rule which states that “the angle of incidence equals the angle of reﬂection” and to simplify matters, let us assume that light hitting a corner of the room is not reﬂected at all. This question was answered in 1995 by George Tokarsky , using the following example. He showed that if you are standing at point A, then you cannot illuminate the whole room — in fact, you cannot illuminate the point B.
This example uses a polygon with 26 sides, but can you ﬁnd one which is smaller?