Mobile Guards

Problem Statement

The problem of mobile guarding (or diagonal guarding as described by O'Rourke) a simple polygon deals with visibility within a polygon. More precisely, given a polygon P of n vertices, what is the maximum number of mobile guards required to cover P.  We defined a mobile guard as a guard patrolling either an edge of P or any diagonal on P's interior.  Furthermore, to cover a polygon we require that for every point xP, that at least one guard can see point x.  We consider a guard to be able to see a point x iff there exists a point y anywhere along the guards patrolling path (remember this is an edge or diagonal of P) for which the straight line segment xy lies entirely within P.

The following is O'Rourke's Theorem for Mobile Guards.
 

Hypothesis

The existence of Toussaint's Class of polygons (shown in Fig. 7) requiring n/4 edge guards gives us a lower bound for the problem.

O'Rourke gives a proof that this indeed is as well the upper bound for gM(n).


Fig. 7 – Toussaint's Class of Polygon's Requiringn/4 Edge Guards


O'Rourke's Method of Proof for Mobile Guards

O'Rourke has proven that n/4 mobile guards are sometimes necessary and always sufficient to cover every polygon of n vertices.  His proof is by induction using the triangulation dual of a given polygon.  He first proves a number of lemmas for mobile guarding in polygons of less than 9 vertices.  He then proceeds to use these as base cases in his induction and well, as he cuts off polygon partitions of 9 or less vertices from the given polygon.  To enable him to do so, he also provides a lemma showing that a sub-polygon of 6, 7, 8, or 9 vertices can always be cut-off from a larger polygon of 10 or more vertices.  As well, one further lemma is given which enables him to perform a pivotal step in the case where he a polygon of 9 vertices is cut-off.

We proceed by exploring each of the required lemmas.  After that, we quickly summarize the results and then apply them for the induction proof.
 
 

Lemmas for Mobile Guarding of Small Polygons

Lemma 1:
Every triangulation graph of a pentagon (5 vertices) can be dominated by a single mobile guard with one endpoint at any selected node.
Proof:
Given any pentagon, there are only 5 possible triangulation duals.  Fig. 9 shows that for any of the 5 possible triangulations, it is possible to dominate the graph using a mobile guard that has one endpoint at vertex 1.

Fig. 9 – Any pentagon can be dominated by a mobile guard with one
endpoint at vertex 1.  (Guards are labelled in yellow)
 
 
 

Lemma 2:

Every triangulation graph of a septagon (7 vertices) can be dominated by a single mobile guard.
Proof:
Given any the triangulation of a septagon, there exists a diagonal stemming from node 1 that partitions the edges of the polygon into either 2 and 5 edges, or 3 and 4 edges (clearly a partition into 1 and 6 edges is not possible since the diagonal is then an existing edge).  Let this diagonal be d (coloured in green in Fig.10).

Case 1: Diagonal d partitions the edges of P into 2 and 5, hence we let d = (1,3).  Diagonal d must support a triangle T (coloured in blue in Fig.10) who's apex is either vertex 4, 5, 6, or 7 (of which only two cases are distinct).

  • If the apex is at 4 (see Fig.10.1), then the pentagon (1,4,5,6,7) can be dominated by a guard with one endpoint at 1 (by lemma 1).  Then the remaining two triangles are dominated since there is  guard at 1.
  • If the apex is at 5 (see Fig.10.2),  then placing a mobile guard between 1 and 5 dominates the quadrilateral (1,5,6,7) and as well dominates the remaining three triangles.
    • Case 2: Diagonal d partitions the edges of P into 3 and 4, hence we let d = (1,4).  The pentagon (1,4,5,6,7) can be dominated by a guard with one endpoint at either 1 or 4 (by lemma 1).  We choose the guard's endpoint depending on which of the two possible triangulations of the quadrilateral is present (see Fig.10.3 and Fig.10.4).

    Fig. 10 – Any septagon can be dominated by a single mobile
    guard.  (Guards are labelled in yellow)
     
     

    Corollary 3:

    Every triangulation graph of a hexagon (6 vertices) can be dominated by a single mobile guard.

     

    Lemma 4:

    Every triangulation graph of an enneagon (9 vertices) can be dominated by two mobile guards where one has an endpoint at any selected node.
    Proof:
    Given any the triangulation of a enneagon, there exists a diagonal stemming from node 1 that partitions the edges of the polygon into either 2 and 7 edges, 3 and 6 edges, or 4 and 5 edges).  Let this diagonal be d (coloured in green in Fig.11).

    Case 1: Diagonal d partitions the edges of P into 2 and 7, hence we let d = (1,3).  Diagonal d must support a triangle T (coloured in blue in Fig.11) who's apex is either vertex 4, 5, 6, 7, 8, or 9 (of which only three cases are distinct).

    Case 2: Diagonal d partitions the edges of P into 3 and 6, hence we let d = (1,4)  (see Fig.11.4).  A mobile guard between 1 and 4 dominates either of the two triangulations of the quadrilateral (1,2,3,4).  Then the septagon S can be dominated by one more mobile guard (by lemma 2).

    Case 3: Diagonal d partitions the edges of P into 4 and 5, hence we let d = (1,5)  (see Fig.11.5).  The pentagon P can be dominated by a single mobile guard with one endpoint at 1 (by lemma 1).  Then the hexagon H can be dominated by a single mobile guard (by corollary 3).


    Fig 11. – Any enneagon can be dominated by a two mobile guards with one endpoint at vertex 1.  (Guards are labelled in yellow)
     
     

    Corollary 5:

    Every triangulation graph of a octagon (8 vertices) can be dominated by two mobile guards where one has an endpoint at any selected node.

    Lemma for Cutting Large Polygons Into Small Pieces

    Lemma 6:
    For every polygon P of n10, there exists a diagonal in P such that  it partitions P into two sub-polygons where one has either 6, 7, 8 or 9 edges.
    Proof:
    For the triangulation T of P, choose a diagonal d with a minimum number of polygon edges with a minimum of 5.  Let k be this minimum and label the vertices of P from 0 to n-1 where d = (0,k).  Diagonal d support a triangle who's apex, let's call it t, that lies somewhere between 1 and k-1.  Since k is minimal, the polygon to either side of our chosen triangle must be smaller than 5.  In other words t4 and k – t4.  Adding these two inequalities gives k8.  Hence, diagonal d is either (0,5), (0,6), (0,7), or (0,8).  This leads to a polygon with either 6, 7, 8, or 9 edges.

    Definition of Edge Contractions

    Let P be a polygon with a triangulation T, and let e be an edge of P defined by endpoint u and v.  An edge contraction of e refers to replacing nodes u and v with a single new node x connected to every node u and v had been adjacent to (see this by comparing Fig.12.1 with Fig.12.4 below).  It should be noted that this is a triangulation graph transformation which allows for deformations in the corresponding polygon.  If we were to try to the same thing directly on a polygon without moving any of the vertices, we might end up with a self-crossing polygon.  The following is a proof that this holds for triangulation graphs.

    Lemma for Edge Contractions

    Lemma 7:
    If T is the triangulation graph of a polygon P, and T' is T with an edge e contracted, then there exists polygon P' such that T' is it's triangulation graph.
    Proof:
    The proof is by construction of P' from P by removing an edge of T to make T' and then showing that P' can be realiazed from T'.
    Let T be the triangulation graph of P with e the corresponding edge to be contracted.  Let u and v be the two endpoints of edge e.  Let y0, y1,…,yi be the vertices connected by diagonals to vertex u starting with y0=v and then sorted in angular order counter-clockwise.  Similarly, let z0, z1,…,zj be the vertices connected by diagonals to vertex v starting with z0=u and then sorted in angular order clockwise (shown in Fig.12.1).

    Introduce a new vertex x somewhere on e.  Connect all vertices y1…yi to x by the following procedure.  Since y1 is the apex of triangle (u,v,y1) and x lies on the edge (u,v), x can be connected to y1 by a straight line segment.  Now remove the diagonal (u,y1).  Now y2 can be connected to x since it lies in the region bounded by the quadrilateral (u,x,y2,y1).  The connection from y2 to x may need to curved but doesn't cross any other edges.  Now remove the diagonal (u,y2).  Continue as such for all y vertices (result shown in Fig.12.2).  Apply the same procedure to connect all vertices z1…zj to x (result shown in Fig.12.3).

    Since the resulting graph is planar (but may include curved edges), we know we can form a corresponding straight-line planar graph in which vertices correspond to vertices and edges correspond to edges of the original graph.  This new graph (Fig.12.4) is called a homeomorphism of the old graph (Fig.12.3).  This follows by Fáry's theorem.

    This construction shows that the triangulation graph T (Fig.12.1) of P can have an edge e contracted to yield a planar graph (Fig.12.3) which upon application of a homeomorphism yields a triangulation graph T' (Fig.12.4).  This triangulation T' can trivially be realized into a polygon P'.


    Fig.12 – An Edge Contraction
     
    Although the usefulness of this lemma may not be immediately obvious, it is pivotal in proving another lemma used in the final proof by induction for mobile guards.  The next lemma depends on this proof for edge contractions.

    Lemma for Mobile Guarding a Polygon with n-1 Guards

    Lemma 8:
    If f(n) combinatorial mobile guards are always sufficient to guard a polygon with a triangulation graph of n vertices.  If we place a single combinatorial vertex guard at one of its node, then f(n-1) combinatorial mobile guards are sufficient to dominate the rest of the graph.
    Proof:
    Let u denote the node at which the single vertex guard is placed in the triangulation graph T of the polygon.  Let v be either of the two vertices connected to u along an edge.

    By the lemma for edge contractions (lemma 7), we can construct a triangulation T' of T by removing the edge (u,v).  Then T' has n-1 nodes and can hence be guarded by f(n-1) combinatorial mobile guards.

    Let x denote the new vertex created in T' that corresponds to the contracted edge (u,v).  If we do not place a guard at vertex x in T', the original set of guards in T with their same placement suffice to dominate their counterparts in T'.
     
     
     

    O'Rourke's Proof for Mobile Guards

    Let's quickly review the 7 lemmas and corollaries that have been presented so far:


    Given these lemmas, O'Rourke's proof by induction follows quite easily.

    Theorem:

    Every triangulation graph T of a polygon of n4 vertices can be dominated by n/4 combinatorial mobile guards.
    Proof:
    Lemmas 1,2,3,4, and 5 for guarding pentagons, hexagons, septagons, octagons, and enneagons, prove that n/4 combinatorial mobile guards are sufficient to guard triangulations with n=5,6,7,8, or 9 vertices.  Hence we'll continue by showing that the theorem is true for triangulations T with n10.  By Lemma 6, we known that any T with n10 can be partitioned by a diagonal d such that two smaller triangulations Tp and T' result, one of which having 6,7,8 or 9 edges (this will be the partition we label as Tp).  We consider each of these possible partition sizes as separate cases:

    Case 1:  Tp is a hexagon (n=6).  By Corollary 3, we have that Tp can be dominated by a single mobile guard.  In this case, T' will have n-4 edges (including the partitioning edge d).  Hence, by the induction hypothesis, T' can be guarded by (n-4)/4 = n/4 -1 combinatorial mobile guards.  Thus together Tp and T' can be dominated by n/4 mobile guards.

    Case 2:  Tp is a septagon (n=7).  By Lemma 2, we have that Tp can be dominated by a single mobile guard.  In this case, T' will have n-5 edges (including the partitioning edge d).  Hence, by the induction hypothesis, T' can be guarded by (n-5)/4n/4 -1 combinatorial mobile guards.  Thus together Tp and T' can be dominated by n/4 mobile guards.

    Case 3:  Tp is an octagon (n=8).  Remember that we are partitioning T by a diagonal to produce the smallest partition with 6,7,8, or 9 edges.  Hence, if we fall into this octagon case, it must be that no other partitioning of T would result in polygons having 6 or 7 edges.  Examination of Fig.13.1 shows that the existence of edges (1,6), (1,7), (2,8), or (3,8) would violate the minimality of our partitioning.  Consequently, the triangle in Tp supported by d must have its apex at vertex 4 or 5.  We'll only consider the case of triangle (1,4,8) which is labelled T in Fig.13.1, since the other case is symmetrically equivalent.  The triangle T further implies the existence of a pentagon (labelled P) within the partition Tp.  At this point, the quadrilateral (1,2,3,4) has two distinct triangulations, each of which is considered as a further sub-case.

    Case 3a:  Fig.13.1 - Tp is an octagon with quadrilateral (1,2,3,4) triangulated by diagonal (2,4).  By Lemma 1, we have that the pentagon P can be dominated by a single mobile guard with one endpoint at vertex 4.  The guard at 4 then dominates the triangle T and the quadrilateral.  So, in this case, T' will have n-6 edges (including the partitioning edge d).  Hence, by the induction hypothesis, T' can be guarded by (n-6)/4n/4 -1 combinatorial mobile guards.  Thus together Tp, which we have shown can be guarded by 1 mobile guard, and T' can be dominated by n/4 mobile guards.

    Case 3b:  Fig.13.2 - Tp is an octagon with quadrilateral (1,2,3,4) triangulated by diagonal (1,3).  Re-attach the quadrilateral (1,3,4,8) to the rest of the triangulation T' (this is denoted by the shaded region in Fig.13.2).  T' now has n-4 edges which, by the induction hypothesis, can be dominated by (n-4)/4 =n/4 -1 guards.  In such a domination, the triangle (1,3,4) must be dominated by a guard which has an endpoint on one of its vertices (this is by definition of domination).  Once again we must consider each of the three possibilities as separate sub-cases.

    • Fig.13.2a denotes the domination by a mobile guard having one end at vertex 1.  This guard also dominates the triangle T and the triangle (1,2,3).  Furthermore, by Lemma 1, we have that the pentagon P can be dominated by a one more mobile guard.  Therefore this reduced Tp and increased T' (the lighter and darker regions of the figure respectively) can be dominated by n/4 mobile guards.
    • Fig.13.2b denotes the domination by a mobile guard having one end at vertex 3.  This guard also dominates the triangle (1,2,3).  Furthermore, by Lemma 1, we have that the pentagon P can be dominated by a one more mobile guard with an endpoint at vertex 8.  This last guard also dominates T.  Therefore this reduced Tp and increased T' (the lighter and darker regions of the figure respectively) can be dominated by n/4 mobile guards.
    • Fig.13.2c denotes the domination by a mobile guard having one end at vertex 4.  This mobile guard's other endpoint must be at either vertex 1, 3 or 8.  The first two cases of which are covered by the previous two sub-cases.  Hence we consider only a mobile guard on (4,8) (the dotted yellow line in the figure).  If we move the given guard to edge (1,8), we see that T' is still dominated by the same number of guards AND now triangle (1,2,3) is guarded as well.  Again by Lemma 1, we have that the pentagon P can be dominated by a one more mobile guard.  Therefore this reduced Tp and increased T' (the lighter and darker regions of the figure respectively) can be dominated by n/4 mobile guards.

    Fig. 13 – Special case for octagons
     
    Case 4:  Tp is an enneagon (n=9).  By Lemma 4, we have that Tp can be dominated by two mobile guards, one with an endpoint coincident with an endpoint of the partitioning diagonal d.  Notice that this implies that one vertex of T' is now under guard by one of our mobile guards for Tp.  In this case, T' will have n-7 edges (including the partitioning edge d).  Since one of T' vertices has a vertex guard on it, by Lemma 8, we have that T' can be dominated by f((n-7) - 1) = f(n-8) combinatorial mobile guards.  Hence, by the induction hypothesis, T' can be guarded by (n-8)/4n/4 -2 combinatorial mobile guards.  Thus together Tp and T' can be dominated by n/4 mobile guards.
     

    Final Result

    Continuing from O'Rourke's theorem for combinatorial mobile guards, it is almost trivial to see that the same n/4 geometry mobile guards always suffice to cover a polygon with n vertices.  This follows from the fact that the theorem holds for any arbitrary triangulation T of the polygon.  Since every triangle of T is guarded by some combinatorial mobile guard, the corresponding mobile guards of the polygon also guard its interior.

    As well, the theorem shows that n/4 geometric lines guards are always sufficient to cover a polygon of n vertices.  This follows directly from the fact that geometric line guards are more powerful that geometric mobile guards.

     

    Algorithmic Implementation

    O'Rourke's proof by induction lends itself directly to implementation of an algorithm for mobile guarding any given polygon.  Following the methods of the proof, we simply iteratively cut-off partitions of 6, 7, 8, or 9 edges from the given polygon. Then, applying the specific steps of the proof, we dominate the cut-off partition by the sufficient number of guards.  Of course O'Rourke's proof shows us that this algorithm is correct.

    The following Java applet demonstrates this direct algorithmic implementation.

    Code Available Here

     

    Corrections to O'Rourke's Proof

    As a final note about mobile guards, I'd like to point out that O'Rourke's proof is not complete.  The error that I've found is very slight and easily corrected.  In fact the above Java implementation incorporates the required changes.

    The error stems from the fact that the base cases for O'Rourke's proof by induction are not fully covered in his paper.  Although the proof claims to be true only for polygons with greater than 4 vertices, it is possible to encounter sub-polygons with 3 vertices due to the partioning of large polygons.  For example, take a polygon of 10 edges from which the smallest possible partitioning splits the polygon into an enneagon and a triangle.  Applying the proof by induction (on the enneagon in the first step) we see that it is expected to be possible to guard the triangle using only n/4 mobile guards.  However, in the case of a triangle n/4 is 0.  This particular case can be used as a counter-example to O'Rourke's proof.

    Upon further inspection (which I will not cover in any depth here), the reader will notice that in fact this is the only case which causes us problems.  Although not directly stated by O'Rourke, a partioning leaving a quadrilateral as the last polygon still holds since a quadrilateral can be dominated by n/4 = 1 mobile guard.  By further examining our only counter-example (the dodecagon), were prompted to see if indeed it can be dominated by n/4 = 2 mobile guards.  This does indeed hold.  The ennagon contained within it, can be guarded by two mobile guards with one endpoint at any given vertex.  We choose that one vertex to be the remaining triangle so that it is guarded as well.

    In conclusion, O'Rourke's proof can be corrected simply by pointing out that the basis case of a quadrilateral requires 1 mobile guard and that the basis case of a dodecagon requires 2 mobile guards.


     
     
     
      
    [NEXT]