An efficient algorithm for the three-guard problem

Abstract: Given a simple polygon with two vertices and , the three-guard problem asks whether three guards can move from to such that the first and third guards are separately on two boundary chains of from to and the second guard is always kept to be visible from two other guards inside . It is a generalization of the well-known two-guard problem, in which two guards move on the boundary chains from to 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 time, and if so generate a walk in time, where denotes the number of vertices of and the size of the optimal walk. This improves upon the previous time bounds and , respectively. Moreover, our results can be used to solve other more sophisticated geometric problems. [Copyright &y& Elsevier]