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)/3
= n/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)/3
= n/3
guards. Hence the **Point Guard Theorem is true** for this case as well.

By Claude Duchesne and Ernesto Posse

October 1998