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^{3}) time and uses O(n^{2}) 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^{2}) 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^{3}) and can be
constructed in Theta(n^{3}) 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.

@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,
}