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 …show more content…
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 …show more content…
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.”
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 …show more content…
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 …show more content…
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.”