hide
Free keywords:
-
Abstract:
The {\em 1-searcher} is a mobile guard whose visibility
is limited to a ray emanating from his position, where
the direction of the ray can be changed continuously with
bounded angular rotation speed. Given a polygonal region
$\poly$ with a specified boundary point $d$, is it possible
for a 1-searcher to eventually {\em see} a mobile intruder
that is arbitrarily faster than the searcher within $\poly$,
before the intruder reaches $d$? We decide this question in
$O(n\log n)$-time for an $n$-sided polygon. Our main result
is a simple characterization of the class of polygons (with
a boundary point $d$) that admits such a search strategy.
We also present a simple $O(n^2)$-time algorithm for constructing
a search schedule, if one exists. Finally, we compare the
search capability of a 1-searcher with that of two guards.
