Abstract
This demostration implements a variation of the art gallery problem where each guard can patrol following a designated wall of the gallery and this gallery restricted to the shape of a monotone polygon and rectilinear monotone polygon. It is based in Iliana BjorlingSachs´s solution published in 1992.
Contents
1. Introduction : The art gallery problem.
2. Problem: Edge guards problem.
4. Algorithm : The algorithm and its analysis.
5. Applet : Demostration of the algorithm.
6. Related links : Computational geometry links and more.
1. Introduction : The art gallery problem
The original art gallery problem was introduced by Victor Klee in 1973 in a discussion with Vasek Chvatal. This first problem asked for the following question: ¿How many guards situated in the vertexs of a gallery with n walls are always enough and sometimes necesary to see all points inside this gallery restricted to the shape of a simple polygon?. Two years later, Chvatal solved it, demostrating that ën/3û guards cover all possible galleries. This was the begining of art gallery problem variation studies; changing gallery shape, changing guard situation and mobility, etc...
2. Problem: Edge guards problem
This problem is a art gallery problem variation, suggested in 1981 by G. Toussaint, where each guard can patrol following a designated wall of the gallery. This kind of guard is called edge guard. The problem is defined as follow. Two points x and y, inside a polygon P, are visible one from the other, when the segment that links both is contained in P. Edge guards cover all points visible from at least one point of the segment where the guard is placed. The problem ask for the necessary number of guards to ensure that all point inside the polygon are visible for at least one edge guard. There is no optimal bound for the required edge guards when the polygon has an arbitrary shape, but Iliana BjorlingSachs proved that é(n2)/5ùedge guards are necessary and sufficient to cover a monotone polygon, and é(n2)/6ùguards for a rectilinear monotone polygon, where n is the number of vertices of the polygon.
3.1. Monotone polygon
To demostrate that é(n2)/5ù
is the tight bound, we first probe that this is the lower bound. Examing
the behavior of the é(n2)/5ù
bound (table 1), we can generalize one monotone polygon which require necessarily
one more edge guard each new five vertices (see figure 1).






































Table 1
Figure 1
Next, in order to demonstrate that é(n2)/5ù is the upper bound, we present an algorithm that assign this number of edge guards to completely cover any monotone polygon.
The algorithm is a Garey`s monotone triangulation algorithm variation that examine all possible configurations of triangles that can occur in each group covered by a edge guard. This algorithm starts at the topmost vertex and moves downward creating triangles by drawing internal diagonals between vertices. As the triangles are formed, they can be grouped in such a way that the union of triangles in each group is covered by one edge guard and every group except one either contains at least five triangles or contains four triangles with a following group containing at least six triangles. The bottom group will consist of any triangles left over the last full group was formed and thus may have fewer than five triangles. Since the triangulation of a P polygon contains n2 triangles, there are at most (n2)/5complete groups and é(n2)/5ù groups total. With one edge guard assigned to each group, the number of guards sufficient to cover P is thus é(n2)/5ù and the upper bound is the same as the lower bound.
3.2. Rectilinear Monotone polygon
To demostrate that é(n2)/6ù
is the tight bound, we first probe that this is the lower bound. Examing
the behavior of the é(n2)/6ù
bound (table 2), we can generalize one rectilinear monotone polygon which
require necessarily one more edge guard each new six vertices (see figure
2).
























Table 2
Figure 2
Next, in order to demonstrate that é(n2)/6ù is the upper bound, we present an algorithm that assign this number of edge guards to completely cover any rectilinear monotone polygon.
The algorithm is a Sack`s monotone quadrilateralization algorithm variation that examine all possible configurations of quadrilaterals that can occur in each group covered by a edge guard. This algorithm starts at the topmost edge and moves downward creating quadrilaterals by drawing internal diagonals between vertices. As the quadrilaterals are formed, they can be grouped in such a way that the union of quadrilaterals in each group can be guarded by one edge guard and every group except the last has at least three quadrilaterals in it. The bottommost group may have fewer than three quadrilaterals since it will consist of any quadrilaterals left unguarded after the last full group was formed. Since the partition of P polygon contains (n2)/2 quadrilaterals, there can be at most (n2)/6 complete groups of at least three quadrilaterals and é(n2)/6ù groups total. With one edge guard assigned to each group, the number of guards sufficient to cover P is thus é(n2)/6ùand the upper bound is the same as the lower bound.
4. Algorithm: The algorithm and its analysis
4.1. Monotone polygon
Steps:
1. Sort vertices of P by decreasing ycoordenate.
Let the vertices in sorted order be p_{0} ,..., p_{n1}
2. Push p_{0} and p_{1} to the
stack.
3. Test p_{i}:
 Let the vertices in the stack be v_{0},...,v_{t}, where v_{0} is the stack base situated in one chain (left or right) and v_{1},...,v_{t} consecutive vertices in the opposite chain.
If p_{i} is adyacent to v_{0} then4. Just a crossdiagonal is created then check if the count of triangles is at least five, if so assign a guard to the correct edge.If p_{i} is adyacent to v_{t} then test angle v_{t 1}v_{t }p_{i}
 Draw crossdiagonals between p_{i} and v_{1},...,v_{t }.
 Pop vertices v_{0},...,v_{t 1} from stack and push vertex p_{i}
If angle at v_{t} is reflex (>180º) thenIf angle at v_{t} is not reflex (<180º) then
 Push p_{i} to the stack.
 Draw sidediagonal between p_{i} and v_{t 1}
 Pop v_{t} from stack.
 Test if exists angle v_{t 2}v_{t1 }p_{i}
4.2. Rectilinear Monotone polygon
Steps:
1. Sort the horizontal edges of P in order of descending
ycoordenate.
Let the edges in sorted order be e_{1} ,..., e_{n/2}
2. Test e_{i}:
If e_{i} is a top edge then push e_{i} in the stack.
If e_{i} is a bottom edge then s < top of the stack thenIf e_{i} and s have at least one endpoint each on the same chain thenIf e_{i} and s lie on opposite chains then
 Draw a sidediagonal between inner endpoints of both edges and s is the next edge to test.
 Draw two cross diagonals between left and right endpoints of both edges.
 Partitioning of the pyramid formed by the edges in the stack and the just created top crossdiagonal. Tracing crossdiagonals from reflex vertices to next reflex vertex below it in the opposite chain.
 Empty stack and push the bottom crossdiagonal.
3. Just a crossdiagonal is created then check if the count
of quadrilaterals is at least three, if so assign a guard to the correct
edge.
5. Applet : Demostration of the algorithm
I have implemented both optimal algorithms in the same program, exactly in a Java applet. This kind of code is capable to run in web environments. First, you need choose the desired kind of polygon, then click with the mouse to situate vertices until close the polygon and last place the guards that will run the proper algorithm.
6. Related links : Computational geometry links and more.
Facultad de Informática de Madrid.
http://www.dma.fi.upm.es/docencia/trabajosfindecarrera/programas/geometriacomputacional/
Godfried Toussaint
http://cgm.cs.mcgill.ca/~godfried/teaching/cgweb.html correspondiente
a
Universidad de Sevilla.
http://ma1.fie.us.es/miembros/almar/docencia/cginfo.htm
Some interesting links in page.
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html
DIMACS Technical Report: A Tight Bound for Edge Guards in Monotone Polygons by Iliana BjorlingSach (92)
DIMACS Technical Report: A Tight Bound for Edge Guards
in Rectilinear Monotone Polygons by Iliana BjorlingSach (93)
Autor
Miguel Ochoa Fuentes