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.

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:

1. an algorithm to compute the minimum number r* of guards needed to sweep an n-vertex polygon that runs in O(n³) time and uses O(n²) 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(n²) 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$ (n³) and can be constructed in $Theta$ (n³) 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.