The Fortress Problem
using Point Guards

 


In this second case, there is less constraint to the position of the guards. Guards can be located at any location in the plane, exterior to the polygon. We call them "point guards", instead of "vertex guards".

Point Guards Theorem [Aggarwal and O'Rourke 1984]

n/3 point guards are sometimes necessary and always sufficient to cover the exterior of a polygon P with n vertices.
 

Necessity proof:

We can prove necessity by showing a particular case. The polygon in figure 1 has 7 vertices. We need at least 3 guards to cover the entire exterior. (7/3 = 3). Therefore, since there exists at least one polygon that needs n/3 guards, we deduce that n/3 point guards are sometimes necessary to cover the exterior of an n-gon.

Figure 1.


 


Sufficiency proof:

The sufficiency proof is more complicated and is due to Shermer (1986). We first prove a simpler lemma (you should see it) and then go on with the proof.

Consider the case in which a polygon P is convex. In this case, we can put two guards on opposite sides far away enough so that each of them can see its side completely. Since n>3 then 2<=n/3. Therefore n/3 are sufficient.

Now consider the case in which P is not convex. Therefore it has at least one "pocket" (a region exterior to the polygon, interior to the convex hull and bound by a hull edge). We should also consider whether the number of vertices in the convex hull is even or odd. In the following, assume an even number of hull vertices.
 

Step 1:
Find the convex hull of P.

Step 2:
Consider a to be the vertex with maximum y coordinate, and b the vertex with minimum y coordinate. If there is more than one vertex with maximum or minimum y coordinates, we can rotate P such that we have unique extreme points.

Figure 2.


 


Step 3:
Add two vertices l and r far enough so that they both see a and b. Consider the line ab. This line divides the plane in two. One such half plane contains l and the other contains r. We say that a point is on l's-side if it is on the half plane that contains l. The same applies for r.

Figure 3.


 


Step 4:
Using the constructed convex-hull (step 1), we triangulate the pockets. Then we add diagonals from l to every convex hull vertex on its side. We do the same for r.

Figure 4.


 


Step 5:
The resulting graph G is consisting of the polygon's vertices, l, r, and the diagonals constructed. G is 3-colorable and therefore the Art Gallery Theorem is applicable. Using this theorem, we know that for a polygon with n+2 vertex, it is sufficient to have (n+2)/3n/3 guards. To see why G is 3-colorable, we can use two colors alternately (say red and blue) for the hull vertices, and then choose the third color for l and r. This is necessary because l and r are adjacent to all the hull vertices. The following figure shows this. Since the pockets are also 3-colorable, G is 3-colorable.

Figure 5.


The Art Gallery Theorem, says that guards should be placed in the least occurring color of the graph. Now, using the argument of the lemma, these guards cover the entire exterior. Hence, the Point Guard theorem is true for this case.

Step 6:
Now we must consider the case in which the number of hull vertices is odd. In this case, the resulting graph is not 3-colorable and the Art Gallery Theorem is not applicable. To see why the graph is not 3-colorable, see the graph in figure 6. The yellow vertex cannot be red, green, or blue, because it is adjacent to points with those colors.

Figure 6.


 


The idea in this case is to modify the graph so that it becomes 3-colorable, and we can apply the Art Gallery Theorem. We do the same process of placing two points (l and r), constructing the convex hull of P, triangulating the pockets, and adding diagonals from l and r to the hull vertices.

Figure 7.


 


Consider any pocket lid in the hull, such as diagonal ce. Since the pocket is triangulated, there is a triangle cde inside the pocket. Now, we rotate P and move r, if necessary, so that the following conditions are met:

1) d is visible from r.
2) r can see a and b, an "antipodal" pair of vertices.
3) dr is not parallel to any polygon edge.

To see that you can always select a position for r that meets the conditions, consider the following polygon, in which the original position of r cannot see d:
 



Figure 8.


 


Now, you can move the point so that it is inside the cone defined by extending dc and de respectively. This guarantees that d is visible from r. We then can move r far away in that direction, so that it can see an antipodal pair of vertices. This pair might be different from the original one.


Figure 9.


 


Moving this point does not invalidates the proof so far, because we already have the triangulation of the pockets, which is independent of the minimum and maximum points (a and b). The only thing that we would have to change would be the "exterior" triangulation. That is the triangulation from r to the convex hull vertices. Note that the other point needs not to be moved unless it does not meet the three conditions above.

Now that we have selected the appropriate r, we can go on. The quadrilateral rcde is convex because c can see e, and r can see d. Erase diagonal ce, and replace it by diagonal rd in the graph.
 


Figure 10.


 


Now, we have an additional vertex in the chain from a to b, so the number of vertices is even, and we can 3-color the graph and apply the Art Gallery Theorem: A polygon with n+2 vertices can be guarded by (n+2)/3n/3 guards. Hence the Point Guard Theorem is true for this case as well.



By Claude Duchesne and  Ernesto Posse
October 1998