We consider the problem of a robot searching for an unknown, yet visually recognizable target in a street. A street is a simple polygon with start and target on the boundary so that the two boundary chains between them are weakly mutually
visible. We are interested in the ratio of the search path length to the shortest path length which is called the competitive ratio of the strategy. We present an optimal strategy whose competitive ratio matches the known lower bound of √2, thereby closing
the gap between the lower bound and the best known upper bound.
This research is supported by the DFG-Project “Diskrete Probleme”, No. Ot 64/8-2.