Sweeping Simple Polygons with a Chain of Guards

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, David C. Lin, Joseph S. B. Mitchell, and T. M. Murali.


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:

  1. 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
  2. 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.
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.

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 Theta (n3) and can be constructed in Theta (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.

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