A Tight Bound for Edge Guards in Monotone and Rectilinear Monotone Polygons

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 Bjorling-Sachs´s solution published in 1992.

Contents

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 Bjorling-Sachs proved that é(n-2)/5ùedge guards are necessary and sufficient to cover a monotone polygon, and é(n-2)/6ùguards for a rectilinear monotone polygon, where n is the number of vertices of the polygon.

3.- Tight bound

3.1.- Monotone polygon

To demostrate that é(n-2)/5ù is the tight bound, we first probe that this is the lower bound. Examing the behavior of the é(n-2)/5ù bound (table 1), we can generalize one monotone polygon which require necessarily one more edge guard each new five vertices (see figure 1).

 n é(n-2)/5ù n é(n-2)/5ù 3 1 12 2 4 1 13 3 5 1 14 3 6 1 15 3 7 1 16 3 8 2 17 3 9 2 18 4 10 2 ... ... 11 2

Table 1

Figure 1

Next, in order to demonstrate that é(n-2)/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 n-2  triangles, there are at most (n-2)/5complete groups and é(n-2)/5ù groups total. With one edge guard assigned to each group, the number of guards sufficient to cover P is thus é(n-2)/5ù and the upper bound is the same as the lower bound.

3.2.- Rectilinear Monotone polygon

To demostrate that é(n-2)/6ù is the tight bound, we first probe that this is the lower bound. Examing the behavior of the é(n-2)/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).

 n é(n-2)/6ù 4 1 6 1 8 1 10 2 12 2 14 2 16 3 18 3 20 3 22 4 ... ...

Table 2

Figure 2

Next, in order to demonstrate that é(n-2)/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 (n-2)/2 quadrilaterals, there can be at most (n-2)/6 complete groups of at least three quadrilaterals and é(n-2)/6ù groups total. With one edge guard assigned to each group, the number of guards sufficient to cover P is thus é(n-2)/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 y-coordenate. Let the vertices in sorted order be p0 ,..., pn-1
2.- Push p0 and p1 to the stack.

• Let the vertices in the stack be v0,...,vt, where v0 is the stack base situated in one chain (left or right) and v1,...,vt consecutive vertices in the opposite chain.
3.- Test pi:
If pi is adyacent to v0 then
• Draw cross-diagonals between pi and v1,...,vt .
• Pop vertices v0,...,vt -1 from stack and push vertex pi
If pi is adyacent to vt then test angle vt -1vt pi
If angle at vt is reflex (>180º) then
• Push pi to the stack.
If angle at vt is not reflex (<180º) then
• Draw side-diagonal between pi and vt -1
• Pop vt from stack.
• Test if exists angle vt -2vt-1 pi
4.- Just a cross-diagonal is created then check if the count of triangles is at least five, if so assign a guard to the correct edge.

4.2.- Rectilinear Monotone polygon

Steps:

1.- Sort the horizontal edges of P in order of descending y-coordenate. Let the edges in sorted order be e1 ,..., en/2
2.- Test ei:

If ei is a top edge then push ei in the stack.
If ei is a bottom edge then s <- top of the stack then
If ei and s have at least one endpoint each on the same chain then
• Draw a side-diagonal between inner endpoints of both edges and s is the next edge to test.
If ei and s lie on opposite chains then
• 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 cross-diagonal. Tracing cross-diagonals from reflex vertices to next reflex vertex below it in the opposite chain.
• Empty stack and push the bottom cross-diagonal.

3.- Just a cross-diagonal 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/cg-web.html correspondiente a

Universidad de Sevilla.
http://ma1.fie.us.es/miembros/almar/docencia/cg-info.htm

Some interesting links in page.
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html

7.- References

DIMACS Technical Report: A Tight Bound for Edge Guards in Monotone Polygons by Iliana Bjorling-Sach (92)

DIMACS Technical Report: A Tight Bound for Edge Guards in Rectilinear Monotone Polygons by Iliana Bjorling-Sach (93)

Autor

Miguel Ochoa Fuentes