The Fortress Problem
using Vertex Guards
In this first case, there is a constraint to the position of the guards. From a fortress point of view, the guards must be placed at the outside corners of the fortress wall. From a geometry point of view, it means that the guards must be on vertices.
Vertex Guards Theorem [O'Rourke and Wood 1983]
vertex guards are sometimes necessary and always sufficient to see the
exterior of a polygon of n vertices. Where
is the ceiling
It suffices to find a polygon that needs n/2 guards. The following figure shows four vertices of a convex polygon and two guards placed on the third vertex from the other. These two guards do not cover the shaded area and placing the guards farther apart would not help. So, placing the guards on every other vertex is necessary for convex polygons.
The two following convex polygons have 8 and 7 vertices respectively. Placing the guards on every other vertex will give four guards in both cases. When "n" is even, no two guards are on the same edge. When "n" is odd, we will need one edge with two guards. Both 8/2 and7/2 equal 4; we found our polygons that needn/2 guards. This was the necessity proof and it shows why we use the ceiling function.
We could think that placing guards on every other vertex is sufficient for all polygons but it is not the case. Some non-convex polygons cannot be treated this way. We will use another strategy here. The figure below shows the simple polygon P with its interior shaded. Our goal is to place n/2 guards in order to cover the exterior of P.
Find the convex hull of P.
Triangulate the portion of the plane that lies inside the convex hull but is exterior to P. In other words, triangulate the pockets of P. We will call the resulting graph G''. It is composed of n nodes corresponding to the n vertices of P.
Add another node called V0 outside the convex hull of P and make it adjacent to every node on the hull (i.e. construct an edge between V0 and all the vertices of the hull). This new graph composed of (n+1) vertices will be called G'.
Choose one of the convex hull vertices, say x, and split it into two vertices x' and x''. Attribute the old x-V0 edge to one of them and create a new edge from the other in order to make both x' and x'' adjacent to V0. This new graph composed of (n+2) vertices will be called G. We see that the interior of P becomes the exterior of G. We claim that G is the triangulation graph of a polygon. This can be seen by "opening up" the convex hull at x' and x'' and moving V0 far enough on the left to see all its connections to be straight lines.
Since G is a triangulation graph of a polygon, it can be 3-colored (3-coloring is more completely explained in this link on the Art Gallery Problem). The least frequently used color, say blue, occurs no more than (n+2)/3 times. If V0 is not colored blue (like on the picture below), then placing the guards on the blue nodes covers the exterior of the original polygon P. This is done with less than n/2 vertex guards since (n+2)/3 is always smaller then n/2. Below, we find 8 vertices in red, 8 in blue and 8 in green (it is a special case). So, we can place the guards either on the blue or the green vertices and 8 is less then 22/2.
However, if the least frequently used color is red and V0 is also colored red (like above), we cannot place the guards on the red nodes since V0 is not part of the original polygon. We will use the second least frequently used color, say blue, and use the following method: