摘要
Guarding in a simple polygon was motivated by art gallery problems. A guard capable of moving along a line segment in a polygon is called a mobile guard. In this paper, we discuss about two different degrees of patrol freedom of mobile guards. First, a guard diagonal is an internal diagonal that a mobile guard moving along the diagonal in a polygon and every interior point of the polygon can be seen by the mobile guard. Second, a guard chord is an internal chord that a mobile guard moving along the chord in a polygon and every interior point of the polygon can be seen by the mobile guard. In this paper, we solve the problem of finding the longest guard diagonal in O(n) time, the shortest guard diagonal in O(nα(n)) and the longest guard chord in O(n) time of a simple polygon P with n vertices, where α(n) is the inverse of Ackermann's function.