CS235 Project: Optimal Covering of Art Gallery

Problem Statement:

Introduction:

Finding the minimal cover of any specific polygon is NP-hard.  There is a well-known approach to finding a guard cover that guarantees no more than n/3 guards - triangulate the polygon, three-color the vertices, and place guards on the vertices with the least-frequently occurring color.  From this, we have the Art Gallery Theorem: For a simple polygon with n vertices, floor(n/3) cameras are occasionally necessary and always sufficient to have every point in the polygon visible from at least one of the cameras.

We looked for other theoretical work regarding the Art Gallery Problem.  Most notable was "Optimal Guarding of Polygons and Monotone Chains"^1., in which the authors discussed techniques for guarding monotone chains with guards on the vertices.  But they dealt with the monotone chains separately.  In a polygon, the chains of vertices might interfere with each other (a guard might not be able to see other vertices on its own chain because the other chain has come between the guard and its charge.  So, we decided to use monotone subdivision, but to develop an algorithm that would examine both the upper and lower chain at the same time.

Another paper, "Guarding the walls of an art gallery,"^2. was about solving the edge-covering problem rather than the interior-covering problem.  It contained analysis of the complexity of both problems (and their relationship to each other).  It turns out that finding the minimal edge cover is also NP-hard.

We have developed an algorithm that is not optimal, but is generally pretty close to optimal (using visual inspection to determine optimal).  We use a more informed approach than triangulation, because we use information about the convexity/concavity of the vertices.  When there are many convex vertices (like in the layouts of actual buildings), our algorithm out-performs triangulation.  We do not guarantee a maximum of n/3 guards, but experimental evidence shows it will be <= n/3 at least 74% of the time.

Definition:

Algorithm:

1. Monotone polygons are useful:  If we know something about the structure of our polygon, we can more easily determine is visible to a single guard.  We have only to deal with two concave chains - so if we know what is happening on each chain, then we know what is happening with all the vertices.
2. One guard can see an entire convex polygon.  Likewise, one guard can cover a convex part of a polygon.

The algorithm consists of three phases:

• Phase 0: Monotone Subdivision.  We used the Plane-Sweep method discussed in class and in the textbook^3..
• Phase 1: Break each monotone polygon into guard areas (one guard per area):

    Sweep through the x-monotone polygon in x-sorted order.
 
• When a concave vertex is encountered, place a guard on it.
• When the next concave vertex is encountered, end the guard area.  Draw a separator from the second concave vertex to the opposite chain.  We can use a vertical separator to guarantee the vertices starting the next guard area will still be convex (in the new guard area).  Or we may be able to draw a separator to the next vertex on the opposite chain.  We do that if it the next vertex in x-sorted order is on the opposite chain and if drawing the separator will cause the vertices to be convex (for both this guard area and the next one).



• When we find an area that is entirely convex, we postpone the guard-placement for Phase 2.
  
  
  
 
• Phase 2: For each convex guard area:
• Check each vertex to see if one has already had a guard placed on it by an adjacent monotone polygon.  If there is one, then the area is already guarded.
• If there is not a vertex with a guard, then look for vertices that are shared by multiple convex areas.  Place a guard on the vertex that is shared by the most convex areas.  Consider all of those areas guarded.

Two of the largest problems with our approach are:

1. We can miss the big picture:  By not looking at the original polygon as a whole, we may place guards in one monotone polygon that can actually see large areas in another monotone polygon.
   
   
   
   
   
   
2. If there is a concave chain (three or more adjacent concave vertices), then it might be optimal to place a guard on a vertex on the opposite chain.  Depending upon the polygon, it could be the case that all of the vertices on the concave chain can be seen by one guard.  This is difficult to handle because we have two chains to deal with at once.  We can detect a concave chain, and we can decide to place guards on the opposite chain, but we may run into problems if we have concave vertices on that chain.
   
   
   
   

Overall Complexity : O(N log N)

• Phase 0 (Monotone Subdivision) : O (N log N)
• Phase 1 (Guarding Monotone Polygons) : O(N)
• Phase 2 (Guarding Vertex Areas) : O(N)

Future Improvements:

• We would like to find a way to make the monotone subdivision more helpful.  Right now, part of out problem is that one monotone polygon does not have any knowledge about its adjacent polygons.  We may end up placing superfluous guard.  If we can determine a way to enhance the monotone subdivision, so that it will give us more information about each subpolygon's part in the whole, then we can cover the polygon with fewer guards.
• We would like to deal with the concave chains more effectively.  We think we can detect them and then use a complicated set of rules to decide where to place the guards.

Project Demo: The Graphical User Interface

Generating the Polygon

1. No intersection: In order to ensure that the dynamically-generated polygon is simple, we will check that no two edges of the polygon intersect.
2. No collinearity: Three collinear vertices will not be allowed.

Output

References:

1. Danny Z. Chen Vladimir Estivill-Castro y Jorge Urrutia, "Optimal Guarding of Polygons and Monotone Chains"
    http://www.site.uottawa.ca/~jorge/online_papers/

2. Guarding the walls of an art gallery (Aldo Laurentini). 

3. M.de Berg, M. van Kreveld, M. Overmars, M.Schwarzkopf ,
Computational Geometry: Algorithms and Applications.