Sweeping Simple Polygons with a Chain of Guards

A. Efrat, L.J. Guibas, S. Har-Peled, D.C. Lin, J.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:

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
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\etal

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.

Postscript file

@inproceedings{eghlmm-sspcg-99,
  author =       {A.~Efrat and L.J.~Guibas and S.~Har-Peled and
                  and D.C.~Lin and J.S.B.~Mitchell and T.M.~Murali},
  title =        {Sweeping Simple Polygons with a Chain of Guards},
  booktitle = SODA_2000,
  pages = {927--936},
  year =         2000,
}

Last updated: Mon Mar 19 10:50:46 CST 2001