9/16/01
Visibility and Illumination Tidbit (08/07/2002)
Prepared by:
Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451
Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)
Imagine that you have to provide security for the interior space on the floor of an art museum which is in the form of a simple polygon. Intuitively you can imagine that there are sensors, also referred to as guards, which are to placed on the floor of the museum. If the beam coming from the sensor is interfered with it sets off an alarm. The sensors can be thought of as sending out beams of laser light or sound which "guard" the points of the floor that they pass over. The beam can cover a full 360 degrees about the point where the beam is located. There are different assumptions one can make about the effect on the signal from the beam hitting a single vertex, several single vertices or even a section of edge of the polygon. We will assume that vertices or edges of the polygon do not interferer with the beam. The beam can not provide security at points that are outside (i.e. the exterior) of the polygon. A typical museum floor is illustrated in Figure 1. The visibility polygon from F extends all the way to a point on side NO. It is good practice to see if you can determine for yourself the visibility polygon from vertex F.
Figure 1
To clarify the meaning of what is going on consider the floor plan of the museum shown in Figure 1. Imagine that a sensor is placed at vertex B of the polygon. What points will the sensor at B protect? Intuitively, we think of what can be seen as all points along lines emanating at B even if the lines pass through points of the boundary of the polygon. Placing a sensor at B allows one to guard points which are inside or on the boundary of the "visibility" polygon from B, which can be described as the polygon with vertices BCDyxPAB. (See Figure 2) In particular the points along the line segment Dy are visible from B despite the point D "interrupting the beam" from B. Although one can place a guard at any point in the interior of the gallery, we will consider only the case where the guards are placed at vertices of the polygon. (See Appendix.)
In Figure 1 the vertices of the polygon with labels F, H, J, L, M are collinear, that is, lie along one straight line.
Figure 2
Given any simple plane polygon with n vertices, what is the largest number number of guards that might be needed for such a polygon? For a fixed polygon P we would be interested in the smallest number of vertex guards necessary to "see" all of the interior of the polygon. However, for a fixed n, we are interested in how "convoluted" the polygon might get, so that we would need a lot of guards.
If the n-gon is convex clearly one only needs one guard and that guard can be placed at any of the vertices of the polygon. We are asking what is the worst number (largest number) of vertex guards that might be needed for any n-gon. This problem was first raised by Victor Klee in 1973. Klee had a guess as to what the answer was but he was not able to prove his conjecture. Can you reconstruct what his conjecture was for yourself?
The answer is that Klee conjectured that the largest integer less than or equal to n/3 guards are sometimes necessary and always sufficient to guard an n-sided museum. (Thus, given a polygon with n sides, floor function of n/3 guards are required for some n-gons and one never needs more than floor function of n/3 vertex guards to guard an n-gon.)
Note that the question raised above is not the question of what is the minimum number of guards to guard a specific polygon with n sides. Rather Klee's question is to determine what is the number of guards that is sometime necessary and always sufficient to guard an n-gon.
Note, that any 3-gon, 4-gon or 5-gon, whether or not it is convex or not will require only one guard. There are, however, some 6-gons which require two guards. Furthermore, there is an easy construction to see that that there are polygons with 3n sides (n>1) which require n guards.
The history of this problem is rather interesting. After Klee made his conjecture, several years went by with the conjecture being open. Eventually, Vasek Chvátal found a proof for the conjecture. This piece of work was very interesting in that it used clever but relatively easy mathematical arguments to resolve the truth of the conjecture. Several years additional went by before Steve Fisk gave a new proof of Klee's conjecture which was amazingly simple.
The strategy of Fisk's proof is easy to describe.
Step 1: Use internal diagonals of the the polygon to triangulate the polygon. This means that every region of the polygon after adding the diagonals is a triangle. (The fact that any plane simple polygon can be triangulated was known for a long time. However, an especially easy proof of this fact can be obtained by using Gary Meister's "Two Ears" Theorem. A vertex v of a polygon is called an ear if the line joining the ends of the two edges at v lies totally within the polygon. Meister's showed that every polygon with at least 4 sides has at least two ears. Using the two ear theorem one can easily use mathematical induction to show that any polygon can be triangulated.
Step 2: Color the vertices of the triangulated graph with 3 colors. In fact, after choosing the three colors that go on the vertices of any triangle, the coloring of all the remaining vertices is completely determined.
Step 3: Assign vertex guards to whichever set of colors in Step 2 has the fewest elements. Since every triangle has all three colors on it, placing guards at the vertices which correspond to the smallest color set will guard the whole polygon.
The floodlight problem is a natural extension of the guards problem motivated by the fact that it is unrealistic to assume that visibility about a point can extend for a full 360 degrees. The nature of this problem is to assume that a vertex of the polygon one can place a floodlight, which opens a fixed angle strictly between 0 and 180 degrees. Thus, one has a question about how to position various fixed angle lights at vertices so as to illuminate the interior of the polygon.
There are many generalizations of the original problem of Klee. O'Rourke's book listed in the references is a very readable account though many more results have been obtained in the period since that book was written.
Appendix:
Visibility region for a guard which not located at a vertex. Notice that a guard can "see" in a full 360 degree range about a point which is a reasonable mathematical assumption but probably not a reasonable "physical assumption."
References:
Chvátal, V., A combinatorial theorem in plane geometry, JCT (B), 18 (1975) 39-41.
Fisk, S., A short proof of Chvátal's watchman theorem, JCT (B) 24 (1978) 374.
Honsberger, R., Mathematical Gems II, Mathematical Association of America, Washington, 1976, p. 104-110.
Meisters, G., Polygons have ears, Amer. Math. Monthly 82 (1975) 648-651.
O'Rourke, J., Art Gallery Theorems and Algorithms, Oxford U. Press, New York, 1987.
O'Rourke, J. Computational geometry column 15, International J. of Computational Geometry and Its Applications 2 (1992) 215-217, (also, SIGACT News, 23 (1992) 26-28.)
O'Rourke, J. Computational geometry column 18, International J. of Computational Geometry and Its Applications 3 (1993) 107-113, (also, SIGACT News, 24 (1993) 20-25.)
O'Rourke, J., Visibility, in Handbook of Discrete and Computational Geometry, ed. J. Goodman and J. O'Rourke, CRC Press, Boca Raton, 1997, Chapter 25.
Rosen, K. (ed.), Handbook of Discrete and Combinatorial Mathematics, CRC. Press, Boca Raton, 2000.
Shermer, T., Recent results in art galleries, Proc. IEEE, 80 (1992) 1384-1399.
Sack, J. and J. Urrutia, Handbook of Computational Geometry, Elsevier, Amsterdam, 1999.
Back to list of tidbits