A Survey of Mobile Guards in Art Galleries
In 1973, in response to a request from Vasek Chvatal for an interesting geometric problem on which to work, Victor Klee responded with the problem of determining the minimum number of guards sufficient to guard an art gallery in the shape of a polygon with n walls. In 1975, Chvatal's publication of his result, , stimulated interest in the problem and its applications. The initial problem is closely related to some problems involving the decomposition of polygons. For example, since each guard in the gallery can see a star-shaped region, determining the number of guards necessary and sufficient to cover the polygon also determines the number of star-shaped regions necessary and sufficient to cover the polygon.
Many different variations of Chvatals Watchmen Problem have arisen. These variations include problems involving polygons with holes, guards that can see in a cone rather than the more often assumed omnidirectional visibility, and three-dimensional art galleries.
Many of the newer variations involve mobile guards. The earliest mobile guard variations involved guards patrolling the gallery along one wall or along line segments between vertices. The emphasis of these mobile guards were that every point of the gallery would be visible by a guard at some point in his patrol. More recently, attention has turned toward problems of pursuit and evasion in which a target tries to evade the guards. In these cases, the goal is often that of searching the gallery in such a way that an intruder must necessarily be detected.
It is mobile guards with which this paper is primarily concerned. Besides the obvious applications of searching buildings to detect intruders, other applications include air traffic control, military strategy, trajectory tracking, surgical applications, and computer-base arcade games.
Chvatals Watchman Theorem
In 1973, in response Victor Klees problem, Chvatal proved in  that n/3 guards will cover the interior of a polygon with n edges and that in some cases, n/3 guards are necessary for the task. In his original paper, he provided an example which required n/3 guards may be required to guard a polygon (see the diagram below). He then proved by induction that that n/3 guards are sufficient to guard any polygon.
Figure 1: Example of gallery requiring n/3 guards
In , Steve Fisk provided a much simpler proof of the theorem. His proof first triangulates the polygon and then uses three colors to color the vertices so that each vertex in any given triangle is a different color from the other vertices. He then counts the number of vertices of each color and chooses the color which colors the fewest vertices. Thus, there can be no more than n/3 vertices of the chosen color. Placing a guard at each vertex of that color covers the polygon with no more than n/3 guards. It is important to note that this procedure is only guaranteed to find a cover of no more than n/3 guards, not the minimum cover.
One variation on the art gallery problems that seems to be completely unexplored is the question of multiple coverage of the gallery. If g guards are sufficient to cover a gallery with n walls, how many guards are necessary to provide multiple coverage of the gallery? That is, how many guards must be placed in the gallery so that at least m guards are visible from every point in the gallery? It is easy to find a gallery which can be covered by one guard if that guard is placed at a particular point, but if the guard is placed elsewhere, even arbitrarily close to the first guard, a portion of the gallery will be hidden from the guard. See Figure 2.
Figure 2: Example of polygon which requires four guards to provide double coverage. The entire polygon is only visible from the vertex.
One common art gallery problem is that of orthogonal or rectilinear galleries. In a rectilinear gallery, any two edges are either parallel to each other or perpendicular to each other. Thus, an orthogonal coordinate system may be defined such that each edge is parallel to either the x-axis or the y-axis.
Figure 3: Example of rectilinear gallery requiring n/4 guards.
In , Kahn, Klawe, and Kleitman show that n/4 guards are sufficient to cover an art gallery in which all the edges are orthogonal. See Figure 3. The largest part of their proof involves showing that any orthogonal gallery may be partitioned into a set of convex quadrilaterals by drawing lines between vertices so that they do not intersect. This proof is similar to Fisks proof since once the gallery may be partitioned into convex quadrilaterals, the vertices may be colored by four colors. Placing a vertex guard at each vertex colored by any one color will cover the gallery. By choosing that color which colors the smallest number of vertices we know that there are no more than n/4 vertices of that color. Thus, n/4 guards are sufficient in an orthogonal or rectilinear gallery.
A rectangular gallery (Figure 4) is one in which the gallery is a rectangle subdivided into rectangular rooms with the stipulation that any two rooms which are adjacent has a door connecting them in which a guard may be placed. Since all points in a room are visible to a guard stationed in the doorway, each guard may maintain surveillance over two rooms simultaneously. In , Czyzowicz, Rivera-Campo, Santoro, Urrutia, and Zaks presented their results on rectangular galleries. They proved that in a rectangular gallery with n rooms, n/2 guards are sufficient to guard the gallery.
Figure 4: A Rectangular gallery with 8 rooms and 4 guards.
Czyzowicz and the others went on to consider an orthogonal gallery which has been decomposed into rectangular rooms. In this case, it is obvious that more than n/2 guards may be required. For example, consider a central rectangular room with a similar room on each side (see Figure 5). One guard may be situated so as to cover both the central square and one of the side rooms. However, each of the other side rooms will require an additional guard since no two side rooms share a common wall. Thus, we have five rooms requiring four guards. They showed that for a rectilinear gallery with v vertices and h holes that is decomposed into r rectangular rooms, (2r + v - 2h - 4) / 4 guards are sufficient.
Figure 5: An orthogonal gallery with 5 rooms which requires 4 guards.
There are some interesting art gallery problems involving mirrors.  includes a brief discussion of these. Assuming the usual physical laws regarding reflection of light rays, the question is whether a polygon with mirrored edges may be lit be a single point source of light. While this is an open question for polygons, in the case of curved surfaces, a simple example shows a case in which there are areas which are not illuminated.
In this example, we have two half circles of different sizes with a common center. At that common center, a point source of light will fail to illuminate the two lobes on each side since each light ray is reflected straight back into the source. However, a point source of light placed elsewhere will be able to illuminate the entire area. A similar example may be used to show that there exist regions in which no single point source of light will illuminate the interior.
Figure 6: A point source of light fails to illuminate part of the area.
One open question by  concerns a forest composed of a finite number of disjoint circular trees whose boundaries are perfect mirrors. The question is whether there is any point from which the rays of a point light source will fail to escape to infinity.
Initially, mobile guards were constrained to patrol either along edges of the polygon or along straight lines wholly contained within the polygon. In the case of mobile guards patrolling along the edges of the polygon, the guards are known as "edge guards". If the guards patrol along straight line segments between vertices, the guards are known as "diagonal guards".
In 1981, Toussaint introduced the idea of having mobile guards in galleries. In particular, he was interested in the minimum number of edge guards necessary to guard the polygon. He conjectured that except for a small number of polygons, n/4 edge guards are sufficient to guard a polygon. Toussaint's original conjecture is still unproven.
ORourke  proved the more general result that the minimum number of mobile guards necessary and sufficient to guard a polygon is n/4 . His proof was a proof by induction similar to Chvatals original proof. He went further and showed that (3n+4)/16 mobile guards are necessary and sufficient to guard orthogonal polynomials.
Zoo-Keeper and Aquarium-Keeper Routes
Another form of mobile guards involves zoo-keeper routes and the related aquarium-keeper routes. In a zoo-keeper problem, a simple polygon P contains a set of convex polygons P1, ..., Pk. The problem is to find the shortest route which has at least one point in common with each of the interior polygons without going inside them. The zoo-keeper routes are intractable in general. , , and  discuss this problem in the special case in which the interior polygons each touch the outer polygon. In this case, the shortest path must travel either clockwise or counter-clockwise and may be found in O(n2) time and in O(n) if each polygon consists of a single edge. The algorithm first constructs an initial zoo-keeper's route and then adjusts the route up to O(n) times to determine the shortest route. When the interior polygons do not touch the boundary of the exterior polygon, the order in which the polygons are visited by the zoo-keeper's path becomes a major problem as there is no natural method to choose the order to visit the polygons.
The aquarium-keeper problem is to find the shortest path in a simple polygon which meets every edge of the polygon. There are two flavors of aquarium-keeper routes. If there are holes in the polygon, the holes are seen as obstacles to avoid, not as additional edges to visit. In polygons without holes, the aquarium-keeper route may be determined in O(n) time. If holes are present, the problem is more complex. When a point is given along the route, the fixed aquarium-keeper's route with holes, the route may be determined in O(n3) time. If no such point is given, determination of the route requires O(n4) time. When there are k aquarium keepers, the route determination requires O(nk+1) time.
Pursuit and Evasion Problems
Pursuit and evasion problems were apparently introduced by Leonardo Da Vinci. The usual pursuit and evasion problems are often expressed in the form of one animal trying to catch another, often by heading straight for the other animal. Such problems often have significant military applications when applied to questions of dogfights between aircraft.
In , Hoenselaers puts a new twist on the problem by considering the case of a dog chasing a hare which is traveling at relativistic speeds (near enough to the speed of light that relativistic effects become important). Usually, the idea is that the dog runs directly at the hare in an attempt to catch the hare. However, in the relativistic case, the dog is not running at the hare, but is instead running toward the point at which it sees the hare. Since the hare is running so fast, by the time the light from the hare has reached the dog, the hare has moved a significant distance. Hoenselaers considered two special cases of the problem. In the first of the two cases, the hare runs in a straight line and the dog is some distance from that line. In the second case, the hare runs in a circle and the dog is some distance from the circle.
Another kind of pursuit and evasion problem of more recent vintage is that of pursuit and evasion on a graph or grid. Typically, these are cops and robbers problems with one or more cops and one or more robbers. In , Goldstein and Reingold studied the complexity of problems in which k cops pursue and attempt to capture one robber on directed and non-directed graphs. They showed that the problem of determining whether k cops can capture a robber on an undirected graph with given initial positions is EXPTIME-complete. They also showed that the problem of determining that the k cops can capture the robber on a strongly connected directed graph (i.e. there is a directed path from each vertex in the graph to every other vertex in the graph) when the cops and then the robber choose their initial positions is also EXPTIME-complete. Some of the open problems on undirected graphs include:
Another pursuit and evasion game is discussed by Neufeld in . In this version, the game is played on an n x m grid. The game uses one or more searchers with limited knowledge and visibility limited to edges in vertices in a straight line from the current position of the searcher. The game also includes a single fugitive with complete knowledge of the positions and strategies of the searchers. The fugitives top speed is one edge per unit of time while the searchers are allowed to move v edges per unit of time. The game is won by the searchers if one or more of the searchers can eventually see the fugitive. Otherwise, the fugitive wins. Two searchers can guarantee a win regardless of how slow they move along the grid. One way that they can do this by working together to systematically search the grid row by row from one side to the other.
Pursuit and Evasion in a Gallery
Interest in problems involving pursuit and evasion in galleries is very recent. The object is generally for one or more pursuit robots to capture or maintain surveillance of an evader. The capture of an invader is usually defined to be detection of the evader by one or more of the guards. The two primary questions which arise in relation to capturing evaders are:
As in the pursuit and evasion problems on grids and graphs, it is helpful to perform the search in such a manner that the intruder cannot sneak past the searchers into a decontaminated area. However, there are cases in which this cannot be helped and areas must be searched again. If the number of searchers is too few, there will always be a strategy by which the intruder can sneak past the searchers and enter areas the searchers have already explored.  gives an example of a polygon in which part of the polygon must be decontaminated many times in the process of searching the polygon. In that case, adding an additional searcher could obviate the need for searching that area multiple times and suggests several questions that may be worth investigating:
In  and , the authors are concerned with using mobile robots to search a space for an unpredictable intruder whose position is unknown and who can move arbitrarily fast. They showed that the worse case bound on the minimum number of pursuers necessary is O(lg n) for a simply-connected free space and provide an example of a simply-connected space that requires W (lg n) pursuers.
They then present a complete algorithm for searching a two dimensional polygonal free space by a single robot. The algorithm decomposes the space in order to identify critical curves where edge visibility changes. This is important for the determination of those areas in the free space where it becomes possible for the evader to slip into a decontaminated area. A binary value is assigned to the edge of each cell in the decomposition to indicate whether or not the area has been decontaminated -- a value of "0" indicates the area is clear and a value of "1" indicates that the fugitive could be hidden behind there. When a solution has been found, every value has been changed to "0".
The cells built from the decomposition process are used to form a cell graph with the vertices representing the cells and the edges showing which cells are adjacent. Each cell is represented by a vertex in the graph. Two cells are connected on the graph if and only if they have a common edge in the free space. Since each cell corresponds to a set of visibility conditions, when moving from one vertex on the graph to another the information state has changed, i.e. new visibility conditions are added or old visibility conditions are removed. The cell graph is then used to construct a graph in the information quotient space which may then be searched to find a solution.
The authors feel that further work along this path along the following lines should be worth exploring:
Another recent problem in moving guards involves using a robot to maintain visibility of a target. In surgery, a somewhat autonomous robot could be used to maintain surveillance over the tools of the surgeon. For example, the surgeon may be unable to directly see what is doing and may rely on a video monitor to see the target area. Instead of requiring one of the operating room personnel to keep the camera aimed at the target, it may be more useful to have a computer perform that task.
In , LaValle, Gonzalez-Banos, Becker, and Latombe deal with this kind of problem. Thus, four conditions are assumed for this problem:
LaValle and the others first considered the case in which the target is predictable. Their algorithm breaks the time interval into K + 1 distinct points in time for which the position of the target is known and creates a space from the Cartesian product of the free space and the set of K + 1 integers from 1 to K + 1. For each k from 1 to K + 1, a standard sweep algorithm is used to map out the points in the free space visible from the target position. The values of a loss functional for each point in the visibility polygon would also be precomputed at this step. Then, at each stage, a cost-to-go function is computed which represents the accumulated cost from starting at the initial configuration and choosing the optimal action each step. From these cost-to-go calculations, the action that must be taken to achieve the next configuration are obtained.
The authors then consider the case of targets that are only partially predictable. A dynamic programming approach could be used for this case also, but the increased complexity led them to consider other approaches. They use feedback based on the current state to compute the control to be applied to move to the next state as in a standard control problem. They also point out that approximation or simplified strategies may be preferable for most real problems in order to cut down on the computational cost. One method they used was a probabilistic uncertainty model to maximize the probability that the target would still be in view at the next step. Another approach they studied was a method of maximizing the minimum time to escape. By using the maximum speed of the robot, they could calculate the minimum time required for the robot to reach the nearest edge of the area visible to the observer.
Some directions for future research in problems of maintaining visibility include:
Another approach to pursuit and evasion was provided by Ichiro Suzuki and Masafumi Yamashita in . They considered the problem of using a mobile searcher to find a mobile intruder in a simple polygon with a limitation placed on the searcher that the searcher could only see along rays in k directions at one time by the use of k flashlights. They were interested in a particular classification of polygons for which a searcher with two flashlights is as capable of finding the evader as a ¥ -searcher (i.e. a searcher who can see in all directions simultaneously). These polygons are termed hedgehogs and have a single convex body with thin hooked pins.
Figure 7: A Hedgehog Polygon
Figure 7: A Hedgehog Polygon
Suzuki and Yamashita showed that if a polygon with n sides is searchable by an ¥ -searcher, then it is searchable by a ( n/2 +1)-searcher.
Two points, x and y, are called separable by a point, z, if the shortest path between x and y contains no points which are visible by z. Three points x, y, and z are called mutually separable if no two points of the three are separable by the third. In the case of a 1-searcher, Suzuki and Yamashita showed that for any polygon which is searchable by a 1-searcher, if x, y, and z are points in the polygon, x, y, and z are mutually nonseparable. In a hedgehog with three pins, the tips of the three pins are mutually separable and thus a 1-searcher is insufficient.
The authors conjecture that any ¥ -searcher polygon is 2-searchable. In the case of hedgehogs, they show that this is indeed true. It would be interesting to find a polygon which is k-searchable, but is not (k-1) searchable for some 3 £ k £ n/2 + 1.
The field of searching art galleries with mobile guards is quite new and open problems exist in abundance. Many of these problems (probably most of the interesting problems) are intractable.
Joseph O'Rourke provides a list of thirty eight open problems involving different aspects of art gallery theorems in . Many of the problems involving The problems he listed involving mobile guards all specifically involve edge guards:
Other open problems include:
The original paper on art gallery problems. Vasek Chvatal gives an example in which n/3û guards are necessary to cover a polygon and presents a proof by induction that n/3 guards are sufficient to cover a polygon.
 L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani, "A Visibility-Based Pursuit-Evasion Problem", Submitted to the International Journal of Computational Geometry and Applications.
 S. M. LaValle, H. H. Gonzales-Banos, C. Becker, and J.-C. Latombe, "Motion Strategies for Maintaining Visibility of a Moving Target" , Submitted to the 1997 IEEE International Conference on Robotics and Automation.
 S. M. LaValle, D. Lin, L. J. Guibas, J.-C. Latombe, and R. Motwani, "Finding an Unpredictable Target in a Workspace with Obstacles", Submitted to the 1997 IEEE International Conference on Robotics and Automation.