Competitive searching in a generalized street

Abstract

We consider the problem of a robot which has to find a path in an unknown simple polygon from one point s to another point t, based only on what it has seen so far. A Street is a polygon for which the two boundary chains from s to t are mutually weakly visible, and the set of streets was the only class of polygons for which a competitive search algorithm was known.