The Algorithm For The Three-guard Problem In A Link-2Visible Polygon

This paper mainly researches the three-guard problem, it can be described as follow:suppose P is a simple polygon, two vertexes on the boundary of P, s and t denote the starting vertex and the ending vertex respectively. Once two points are given, the boundary of P is divided into two polygon chains:L and R. The three-guard problem asks for a walk of three guards move from s to t, finially complete the walk and expel the possible intruder from t. During the walk, two guards move on the chain L and R respectively, while the last guard moves in the polygon. Besides, it requires two adjacent guards are kept visible from each other at every moment of the walk.First, this paper introduced several classic problems of Computational Geometry. Then it researched the three-guard sweep mechanism stressly based on some relevant basic knowledge. To solve the three-guard problem, we analyzed the solution method of the two-guard problem. By using the one-to-one correspondence between the structure of the restrictions placed on the motion of two guards and the one placed on the motion of three guards, we introduced the concept of link-2visibility and link-2-ray shots, proposed the necessary and sufficient condition of the three-guard-walkable polygon and generated a walk schedule if it exists. The algorithm in this paper can decide whether there exists a solution for the three-guard problem in O(nlogn) time, and if there exists, generate a walk in O(nlogn+m) time, where n denotes the number of vertexes of P and m(≤n2) is the size of the optimal walk. This algorithm improves upon the previous bounds O(n2) and O(n2logn). At the end of this paper, we constructed the data structure and accomplished the algorithm task under the previous theoretical work.