Home Bookmarks Papers Blog

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:

  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\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 : PDF
  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 modified: Wed Jul 20 15:57:40 CDT 2011