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


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.