The Two-Guard Problem Revisited and Its Generalization

摘要

Given a simple polygon P with two vertices u and υ, the two-guard problem asks if two guards can move on the boundary chains of P from u to υ, one clockwise and one counterclockwise, such that they are mutually visible. By a close study of the structure of the restrictions placed on the motion of two guards, we present a simpler solution to the two-guard problem. The main goal of this paper is to extend the solution for the two-guard problem to that for the three-guard problem, in which the first and third guards move on the boundary chains of P from u to υ and the second guard is always kept to be visible from them inside P. By introducing the concept of link-2-ray shots, 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. We can decide if there exists a solution for the three-guard problem in O(n log n) time, and if so generate a walk in O(n log n + m) time, where n denotes the number of vertices of P and m (≤ n~2) the size of the optimal walk.