The original Art Gallery problem, as posed by Klee, refers
to guard placements within an art museum. Suppose you have the floor
plan for an art gallery. Assuming your art gallery has only one level
and no doors to separate its rooms, you can represent it by a two dimensional
polygon with n vertices representing the room's corners.
The question then, is how many stationary guards are needed to keep
every part of the art gallery under surveillance? Our stationary
guards have the ability to keep watch 360
around them at all times
and as far as needed. Obviously, however, they cannot be expected
to see through walls.
Fig.1 - An Art Gallery requiring 3 Stationary Guards
The notion of what a guard can see is referred to as visibility from
a point. Geometrically speaking, for a polygon P, we say that a point
x can see another point y (where both x and y
P) if and only if the straight line segment joining them is nowhere
exterior to P. Furthermore, we say that a set of guards covers P,
if and only if every point z P is visible from at least
one of the points where a guard is positioned.
Fig. 2 – Point y is Visible from Point x
Finally, the question we are looking to answer is: What is the minimum
number of guards required to cover any polygon of n vertices.
We'll denote this by g(n).
Chvátal was the first to find the solution to the art
gallery problem. However, his induction proof is quite involved and
will not be covered. Three years later, Fisk found a remarkably simple
and beautiful proof for the same problem.
Fisk first arbitrarily triangulates the given polygon P. This
involves partioning the entire interior of P using only triangles, through
the addition of diagonals between existing vertices of P. These diagonals
do not intersect themselves of the edges of P. Fig.3 shows an example
of arbitrary triangulation of a polygon (the proof of polygon triangulation
is not covered here).
Fig.3 – An Arbitrary Triangulation of Polygon P
Once triangulated, our polygon P can be three-coloured by assigning
one of the three colours, red, green and blue, to each of the vertices
of P. Assignment of the colours is done such that no triangle has
two or more vertices of the same colour. This can be done by arbitrarily
choosing two adjacent vertices of P and giving them two different colours.
The colouring of the rest of P is then fully determined. Proof that
this can always be done is given by the three-colouring theorem but is
not included here.
Fig.4 – Three-Colouring of Polygon P
Note that by virtue of three-colouring, every triangle within the triangulation
of P has a red, green, and blue vertex. Furthermore, this implies
that if one chooses a given colour, say red, every triangle within P has
a vertex of that colour. Also note that every point within a triangle
is under guard if one of the triangle's vertices is a guard. Hence,
it is a simple matter of choosing the colour, within our three-coloured
triangulation, which occurs the least and then positioning guards at every
vertex of that colour. In this case, we have 4 reds, 4 greens, and
3 blues. We therefore position guards over all the blue vertices
to ensure that every triangle of P is guarded.
Fig. 5 – Guard Positioning within Polygon P
How many guards does this algorithm yield? Since there are n
vertices and 3 colours, by the pigeon-hole principle, we know that there
is at least one colour that has at most 
n/3
.
Hence we have at most n/3 guards. (This
is indeed the case in our example where we have 11 vertices and 11/3
= 3 guards)
The reader should note that this does not necessarily (and in our example
does not) give an optimal guard positioning within the polygon. However,
it does prove an upper bound of n/3 guards
for the problem. Chvátal put forth a class of polygons (shown
in Fig.6) requiring a minimum of n/3 guards
to show that in some cases this number was necessary.
Fig. 6 – Chvátal's Comb
The existence of such a class of polygons shows that indeed, n/3
stationary guards are sometimes necessary and always sufficient to guard
any simple polygon of n vertices.
Notice that the given theorem abstracts the problem of visibility within
a polygon to that of domination of the polygon's triangulation graph.
That is to say, positioning guards within the triangulation of a polygon
so that it is fully dominated suffices to cover the corresponding polygon
itself. Notice as well, that here we used a restricted form of stationary
guards, namely vertex guards. More general stationary guards (positioned
anywhere within the polygon) could be used, but the existence of Chvatal's
Comb class of polygons is sufficient to show that they have the same lower
bound for guarding and hence have the same power as vertex guards.
Toussaint proposed an interesting variant of the art gallery
problem. He proposed to change the power of the guards so rather
than be stationary at a point, they can patrol along any straight line
segment that lies entirely within the Polygon P. In this case, a
point x P can be seen by a guard if there exists some point
y on the guards patrolling path such that x can clearly be
seen from it. This is the notion of weak visibility introduced by Avis
and Toussaint. Note that this does not mean that the point is visible
from everywhere on the guard's path (this is referred to as strong visibility),
it suffices that it is visible from at least one point along the path.
As with the original art gallery theorem, we may constrain the allowable
positions of the guard paths. The three most popular types of guards
are edge guards, mobile guards, and line guards. Edge guards are
limited to patrolling existing edges of a polygon. Mobile guards
(or diagonal guards as described by O'Rourke) are limited to patrolling
either edges or diagonals of the polygon. And line guards, the most
powerful, may patrol any line segment entirely contained within the polygon.
The associated problems for each of these types of guards asks us to find
the functions gE(n), gM(n),
and gL(n), which, respectively, give us the minimum
number of the given type of guards required to cover a polygon of n
vertices. Since, respectively, each type of guard is less powerful
than the next, we have the following inequality: gE(n)
gM(n) gL(n).
The original problem proposed by Toussaint was that dealing with edge
guards. He conjectured that gE(n) = n/4
except for a small set of polygons with relatively few vertices.
Although he could offer no direct proof, he did exhibit the following class
of polygons which indeed does provide a lower bound of gE(n)
n/4 for the problem.
Further, Paige and Shermer offered two polygons requiring more than n/4
guards, however, these do not generalize.
Fig. 7 – Toussaint's Class of Polygon's Requiring
n/4 Edge Guards
|
Fig.8 – Paige and Shermer's Polygon's Requiring (n+1)/4
Edge Guards
|
O'Rourke was the first to make progress on the problem by proving that
gM(n) = n/4.
We shall explore his proof in the following section and then proceed to
look at some results for gE(n).