We consider the problem of locating a continuously-moving target using a group of guards moving 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. We develop algorithms that sweep such a chain of guards through a polygon to locate the target.
Our two main results are the following:
We develop two other techniques to approximate r*. Using O(n2) time and space, we show how to sweep the polygon using at most r* + 2 guards. We also show that any polygon can be swept by a number of guards equal to two more than the link radius of the polygon.
- an algorithm to compute the minimum number r* of guards needed to sweep an n-vertex polygon that runs in O(n3) time and uses O(n2) working space, and
- a faster algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2) <= r* <= r and P can be swept with a chain of r guards.
As a key component of our exact algorithm, we introduce the notion of the link diagram of a polygon, which encodes the link distance between all pairs of points on the boundary of the polygon. We prove that the link diagram has size (n3) and can be constructed in (n3) time. We also show link diagram provides a data structure for optimal two-point link-distance queries, matching an earlier result of Arkin et al.
As a key component of our O(n log n)-time approximation algorithm, we introduce the notion of the ``link width'' of a polygon, which may have independent interest, as it captures important structural properties of simple polygons.
You can download the SODA submission.