Open Collections

Optimally sweeping convex polygons with two and three guards

University of British Columbia

Given a polygon P, we considered the problem of finding the shortest total paths for two and three mobile guards to cover P. In our definition of the problem, we do not limit the movements of the guards. The guards are allowed to start their paths at any point on the polygon, cross the interior or intersect each other's paths if necessary. A polygon P is covered by two guards if every point in P is on the line that connects the guards at some point in time. We proved that if the polygon is convex, the optimal sweep limits the paths of the guards to the perimeter of the polygon. In the optimal solution the guards may start their paths at the end-points of the longest edge of P and end their paths at the end-points of the second longest edge in P, visiting the n-2 other edges along the way. Finding such a path takes O(n) time. With three, the guarding problem is defined differently. In the three guard problem a point is covered if it is on the triangle formed by the guards at some point in the sweep. We found that even in convex polygons in some cases crossing the polygon makes the sweep shorter. However, we showed that the optimal sweep is always simple (i.e., the guards paths do not cross one another). By recognizing the conditions where interior paths are beneficial we were able to present an algorithm to find the optimal 3-guard path in O(n⁵) time.

Text

2010-04-30

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/24248

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/