Sweeping simple polygons with the minimum number of chain guards

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 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(n2) 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*n2) time. Our results improve upon the known time bounds by a linear factor.