Position Independent Street Searching. C.A. Hipke,
and A López-Ortiz. Workshop on Algorithms and
Data Structures, 1999. PostScript
file
Abstract.
A polygon P is a street if
there exist points (u,v) on the boundary such that
P is weakly visible
from any path from u to v.
Optimal strategies have been found for on-line searching of streets
provided that the starting position of the robot is s=u and the
target is located at t=v. Thus a hiding target could foil the
strategy of
the robot by choosing its position t in such a manner as not to
realize a street.
In this paper we introduce a strategy with a constant competitive
ratio to search a street polygon for a target located at an arbitrary
point t on the boundary, starting at any other arbitrary
point s on the boundary. We also provide lower bounds for this
problem.
This makes streets only the second non-trivial class of polygons (after
stars) known to admit a constant-competitive-ratio
strategy in the general position case.