(n+1)/3
point guards are sufficient to cover the exterior of a polygon P.

__Proof__:

Consider *a* to be the vertex with maximum *y* coordinate
and *b*, 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 1.

Add two vertices *l* and *r* below *b*, and far enough
so that they both see *a. *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*-side's if it
is on the same half plane that contains *l*. The same applies for
*r*.

Figure 2.

Construct the convex
hull of the polygon, and triangulate
the pockets (region inside the convex hull but exterior to the polygon).
Then add diagonals from *l* to every convex hull vertex on its side.
Do the same for *r*.

Figure 3.

Then use the same method applied in the Vertex
Guards Theorem, for "converting the exterior to interior". Split vertex
*a* into two vertices. Make the new vertex *a'* so that one of
the edges adjacent to *a*, say the edge on *r*-side, becomes
adjacent to *a' *instead. Also, the old diagonal from *r* to
*a* now connects *r* to *a'*. The resulting polygon *P'
*becomes "opened".

Figure 4.

Since there is no edge between *a* and *a'*, the interior
of the original polygon is now exterior so that the resulting polygon has
n+3 vertices (the original n vertices plus *l* plus *r* plus
*a'*). This polygon is triangulated because it consists of the pockets,
which we already triangulated, and the triangles formed by the diagonals
between *l* and *l*-side convex hull vertices, and the diagonals
between *r* and *r*-side convex hull vertices.

Since the resulting polygon is triangulated it can be covered with (n+3)/3
= (n+1)/3
guards because of the Art
Gallery theorem. What about the rest of the plane, outside the
original polygon? Do these guards cover it? Let's consider *l*'s-side.
If there is a guard on* l*, it covers the part its half-plane that
is neither in *P *nor in *P'*, because we selected *l *such
that it could see both *a *and* b.*

If there is no guard in *l*, the guard must be in one of the convex
hull vertices on *l*'s-side because every edge in the convex hull
(on *l*'s-side) forms a triangle with *l*. In order to cover
such a triangle, we need a guard on at least one endpoint of the edge.
Since that is true for every edge on the chain from *a* to *b*
(on *l*'s-side), the guards on these edges will cover the exterior.
The same argument applies for *r*'s-side. Either way, we do not need
to add more guards to cover the rest of the plane, so (n+1)/3
guards can cover the exterior.