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]
n/2
vertex guards are sometimes necessary and always sufficient to see the
exterior of a polygon of n vertices. Where
is the ceiling
function.
Necessity proof:
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.
Sufficiency proof:
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.
Step 1:
Find the convex
hull of P.
Step 2:
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.
Step 3:
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'.
Step 4:
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.
Step 5:
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: