An efficient algorithm for the three-guard problem

Given a simple polygon PP with two vertices uu and vv, the three-guard   problem asks whether three guards can move from uu to vv such that the first and third guards are separately on two boundary chains of PP from uu to vv and the second guard is always kept to be visible from two other guards inside PP. It is a generalization of the well-known two-guard   problem, in which two guards move on the boundary chains from uu to vv and are always kept to be mutually visible. In this paper, we introduce the concept of link-2-ray shots  , which can be considered as ray shots under the notion of link-2-visibility. Then, we show a 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, and generalize the solution for the two-guard problem to that for the three-guard problem. We can decide whether there exists a solution for the three-guard problem in O(nlogn)O(nlogn) time, and if so generate a walk in O(nlogn+m)O(nlogn+m) time, where nn denotes the number of vertices of PP and m(≤n2) the size of the optimal walk. This improves upon the previous time bounds O(n2)O(n2) and O(n2logn)O(n2logn), respectively. Moreover, our results can be used to solve other more sophisticated geometric problems.