Sweeping Simple Polygons with the Minimum
Number of Chain Guards

Xuehou Tan
Tokai University, 317 Nishino, Numazu 410-0395, Japan

Abstract

We study the problem of detecting a moving target using a group of k+1 (k is a positive integer) mobile guards inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that consecutive guards along the chain are mutually visible. In this paper, we introduce the notion of the link-k diagram of a polygon, which records all the pairs of points on the polygon boundary such that the link distance between any of these pairs is at most k, and a transition relation among minimum-link (k) paths as well. An O(n²) time algorithm is then presented to compute the minimum number r^* of guards required to detect the target, no matter how fast the target moves. Moreover, a sweep schedule can be reported in O(r^* n²) time. Our results improve upon the previously known time bounds by a linear factor.