Site Loader
Rock Street, San Francisco

MobileLazy Guards Kailan PatelNottingham Trent UniversityN0672831December 10, 2017  ABSTRACTTheArt Gallery problem is well known in computational geometry and a real lifeproblem is the Lazy Guard Problem; “Given a polygon, choose a minimum number ofstations (points) in the polygon such that a mobile guard that visits allstations will guard the entire polygon.” 1 Furthermore, a polygon that can beguarded with an X number of stations is said to be lazy X guardable.  Keywords: Lazy Guards, Simple Lazy Guards, Mobile Guards, Stations, PiecewiseLinear Chain.

  IntroductionThe Lazyguard problem involves mobile guards and was first introduced by Paul Colly,Henk Meijer and David Rappaport. It is another variation to the Art Galleryproblem, due to it being real life. It takes into account real life guards andtheir technique to protecting the polygon, which may not be as the employer wants.

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

In this particular example there are several stations that the guard will needto check on a regular basis, thus leading to more regular patrols. In simplerterms, the lazy guard problem is as follows; while the guards are travelling toeach station, what is the minimum number of guards required to ensure everypoint in the polygon is visible. The main results of the paper suggest that, a simplepolygon that can be guarded with an X number of stations is said to be lazy Xguardable and that if stations are places on the edge of the polygon it willmean that the polygon will be guarded more efficiently.  Lazy guarding a simple polygonThe main aim of this paper is to answer thefollowing question; Question 1: “Given a polygon, choose aminimum number of stations (points) in the polygon such that a mobile guardthat visits all stations will guard the entire polygon.” 1 Thereare six key theorems/lemmas to the lazy guard problem; Theorem 1: “For simple polygons, ordering stations does not matter and the classof lazy k guardable simple polygons is identical to the class of short lazy kguardable simple polygons.

” 1 Proof: Ina simple polygon as shown below (see Figure 1.), 2 stations are required toguard this shape and is lazy guardable from A to B. Take any point P on thepolygon and this point is guarded during the route of the guard from station Ato B, then extend a straight line from the point P through the route AB all theway 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 thisline regardless of the route taken to get in-between the two stations, thisshows that the guards will be guarding point P, thus guarding the entirepolygon. This means the minimum number of stations required would be 2 to guardthe 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 ofstations does matter. For example, as seen in the second polygon (see Figure2.) this polygon requires 3 stations. We assume that the guards will start andfinish 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 toanother covering all stations ABCA (the short lazy guard problem). However, withthree points, the order in which each station is visited makes a difference. Forexample, the guard is unable to go from ACABAC, as this will mean not allpoints on the polygon P are visible at all times. For polygons only containingone 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 thepolygon (seen in figure 2), however for a simple polygon that is lazy twoguardable this is not necessary.  Lemma 2: “If a polygon is guardable using k stations, it can also be guardedwith k stations located on the boundary of P.” 2 Definition 2: Apiecewise linear chain is a connected series of lines ending on itself that is formed by a sequence of straight-line segment. Proof:Theguard’s polygon is a piecewise linear chain, extend the end segments of thechain until they reach the edge of the polygon. The stations have to be movedto where the chain reaches the edge of the polygon, which includes the originalguard’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 thesame 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:Separatethe polygon into separate parts, then determine the smallest number of pointssuch that each part of the polygon has at least one point in it. An algorithmcan be used to do this in linear time due to the optimal algorithm for the twoguarded problem due to 4.

This problem is solved in linear time by the circlecover minimization problem 3 and is described in terms in covering a set ofcircle arcs with a minimum number of points. Thus leading to the followingtheorem 6. Theorem 6: “An optimal placing of stations to lazy guard a polygon can be found inlinear time.” 2 ConclusionTo conclude, the mobile lazy guard problemdoes reduce the number of guards required to guard the museum as only one guardwould be needed however this means not all points in the polygon will bevisible at all times if there is only one mobile guard which means not allpoint on the polygon will be visible to the guard at all times thus meaning theoriginal art gallery problem 2 is not solved.

Therefore, they require thesame number of guards as they would for a normal art gallery however they couldhave more guards walking simultaneously in-between the stations thus whichwould mean that all points of the polygon would be visible at all times. Ibelieve there are better more efficient extensions to the art gallery problemthat will guard the polygon, such as the fortress problem 5 or the prisonyard problem 6. Finally, to answer the main question proposed, the minimumnumber of stations that is required in the polygon is the same number of guardsthat 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’sUniversity.

Kingston, Ont. Canada(1995).2Jorge Urrutia.

Art Gallery and Illumination Problems. Dept. Instituto deMatem´aticas, UnivresidadNacional Aut´onoma de M´exico. Mexico (2004).3C.C.

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

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

4P.J.Heernan. An optimal algorithm for the two-guard problem. Proc.

9th Annu.ACMSympos. Comput. Geom. (1993) 348{358.5S.M. Yiu.

A Generalized Fortress Problem Using K-Consecutive VertexGuards.  Dept. of Computer Science.University of Hong Kong. 6Z. Furedi and D. J.

Kleitman, “The prison yard problem,” Combinatorica, vol.14, pp. 287–300, 1994.

Post Author: admin

x

Hi!
I'm Eric!

Would you like to get a custom essay? How about receiving a customized one?

Check it out