Mobile

Lazy Guards

Kailan Patel

Nottingham Trent University

N0672831

December 10, 2017

ABSTRACT

The

Art Gallery problem is well known in computational geometry and a real life

problem is the Lazy Guard Problem; “Given a polygon, choose a minimum number of

stations (points) in the polygon such that a mobile guard that visits all

stations will guard the entire polygon.” 1 Furthermore, a polygon that can be

guarded with an X number of stations is said to be lazy X guardable.

Keywords: Lazy Guards, Simple Lazy Guards, Mobile Guards, Stations, Piecewise

Linear Chain.

Introduction

The Lazy

guard problem involves mobile guards and was first introduced by Paul Colly,

Henk Meijer and David Rappaport. It is another variation to the Art Gallery

problem, due to it being real life. It takes into account real life guards and

their technique to protecting the polygon, which may not be as the employer wants.

In this particular example there are several stations that the guard will need

to check on a regular basis, thus leading to more regular patrols. In simpler

terms, the lazy guard problem is as follows; while the guards are travelling to

each station, what is the minimum number of guards required to ensure every

point in the polygon is visible. The main results of the paper suggest that, a simple

polygon that can be guarded with an X number of stations is said to be lazy X

guardable and that if stations are places on the edge of the polygon it will

mean that the polygon will be guarded more efficiently.

Lazy guarding a simple polygon

The main aim of this paper is to answer the

following question;

Question 1: “Given a polygon, choose a

minimum number of stations (points) in the polygon such that a mobile guard

that visits all stations will guard the entire polygon.” 1

There

are six key theorems/lemmas to the lazy guard problem;

Theorem 1: “For simple polygons, ordering stations does not matter and the class

of lazy k guardable simple polygons is identical to the class of short lazy k

guardable simple polygons.” 1

Proof:

In

a simple polygon as shown below (see Figure 1.), 2 stations are required to

guard this shape and is lazy guardable from A to B. Take any point P on the

polygon and this point is guarded during the route of the guard from station A

to B, then extend a straight line from the point P through the route AB all the

way to the edge of the polygon, thus dividing the polygon into two segments,

one segment containing A and the other containing B. The guard will cross this

line regardless of the route taken to get in-between the two stations, this

shows that the guards will be guarding point P, thus guarding the entire

polygon. This means the minimum number of stations required would be 2 to guard

the whole of this polygon.

Figure 1

Definition 1: Short lazy guard problem;

Guards will pick the shortest route to get in-between stations.

However,

on the other hand to guard a polygon that requires k stations (k ³ 3), the ordering of

stations does matter. For example, as seen in the second polygon (see Figure

2.) this polygon requires 3 stations. We assume that the guards will start and

finish at the same point and they will want to minimise the distance they walk,

therefore the guard will pick the shortest route to get from one station to

another covering all stations ABCA (the short lazy guard problem). However, with

three points, the order in which each station is visited makes a difference. For

example, the guard is unable to go from ACABAC, as this will mean not all

points on the polygon P are visible at all times. For polygons only containing

one or two stations, the ordering will not make a difference.

Figure 2

Furthermore,

some two guardable polygons require the guards to be on the interior of the

polygon (seen in figure 2), however for a simple polygon that is lazy two

guardable this is not necessary.

Lemma 2: “If a polygon is guardable using k stations, it can also be guarded

with k stations located on the boundary of P.” 2

Definition 2: A

piecewise linear chain is a connected series of lines ending on itself that is formed by a sequence of straight-line segment.

Proof:

The

guard’s polygon is a piecewise linear chain, extend the end segments of the

chain until they reach the edge of the polygon. The stations have to be moved

to where the chain reaches the edge of the polygon, which includes the original

guard’s problem therefore any point P on the polygon can be guarded.

Figure 3

Theorem 3: “Any simple polygon which is lazy guardable may be guarded with the

same number of stations placed on the boundary of the polygon.” 1

Lemma 4: “A simple polygon is lazy k guardable (with k ³ 2)

if and only if it admits a choice of k end points so as to form a k-street.”

1

Lemma 5: “The chain C (s, t) is weakly visible from C (s, t) if and only if C

(s, t) does not contain a clockwise or counter-clockwise component.” 1

Proof:

Separate

the polygon into separate parts, then determine the smallest number of points

such that each part of the polygon has at least one point in it. An algorithm

can be used to do this in linear time due to the optimal algorithm for the two

guarded problem due to 4. This problem is solved in linear time by the circle

cover minimization problem 3 and is described in terms in covering a set of

circle arcs with a minimum number of points. Thus leading to the following

theorem 6.

Theorem 6: “An optimal placing of stations to lazy guard a polygon can be found in

linear time.” 2

Conclusion

To conclude, the mobile lazy guard problem

does reduce the number of guards required to guard the museum as only one guard

would be needed however this means not all points in the polygon will be

visible at all times if there is only one mobile guard which means not all

point on the polygon will be visible to the guard at all times thus meaning the

original art gallery problem 2 is not solved. Therefore, they require the

same number of guards as they would for a normal art gallery however they could

have more guards walking simultaneously in-between the stations thus which

would mean that all points of the polygon would be visible at all times. I

believe there are better more efficient extensions to the art gallery problem

that will guard the polygon, such as the fortress problem 5 or the prison

yard problem 6. Finally, to answer the main question proposed, the minimum

number of stations that is required in the polygon is the same number of guards

that is needed to guard the polygon using the art gallery theorem.

References

1 Paul Colley, Henk Meijer, David Rappaport.

Motivating Lazy Guards.

Dept. Compuing and information Science, Queen’s

University. Kingston, Ont. Canada(1995).

2

Jorge Urrutia. Art Gallery and Illumination Problems. Dept. Instituto de

Matem´aticas

, Univresidad

Nacional Aut´onoma de M´exico. Mexico (2004).

3

C.C.Lee and D.T.Lee. On a circle-cover minimization problem.

Inform.Process.Lett. 18 (1984) 109{115.

4

P.J.Heernan. An optimal algorithm for the two-guard problem. Proc.9th Annu.ACM

Sympos. Comput. Geom. (1993) 348{358.

5

S.M. Yiu. A Generalized Fortress Problem Using K-Consecutive Vertex

Guards. Dept. of Computer Science.

University of Hong Kong.

6

Z. Furedi and D. J. Kleitman, “The prison yard problem,” Combinatorica, vol.

14, pp. 287–300, 1994.