Abstract: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

- an algorithm to compute the minimum number
r*of guards needed to sweep ann-vertex polygon that runs inO(ntime and uses^{3})O(nworking space, and^{2})- a faster algorithm, using
O(nlogn)time andO(n)space, to compute an integerrsuch that max(r - 16, 2) <= r* <= randPcan be swept with a chain ofrguards.r*. UsingO(ntime and space, we show how to sweep the polygon using at most^{2})r* + 2guards. 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.As a key component of our exact algorithm, we introduce the notion of the

link diagramof 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$Theta$ (nand can be constructed in^{3})$Theta$ (ntime. We also show link diagram provides a data structure for optimal two-point link-distance queries, matching an earlier result of Arkin et al.^{3})As a key component of our

O(nlogn)-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.

T. M. Murali (murali@cs.stanford.edu) Jul 14, 1999