Walking an unknown street with bounded detour (Q1194307): Difference between revisions

A special shortest path problem on the basis of local information is considered. Let \(P\) be a simple polygon with two distinguished vertices, \(s\) and \(g\), and let \(L\) and \(R\) be the oriented boundary chains leading from \(s\) to \(g\). Then \((P,s,g)\) is called a street iff each point of \(L\) can be seen from at least one point of \(R\), and vice versa. Relations to similar concepts are discussed. For a mobile robot with local information (visibility polygons) the author describes a strategy for finding a short path from \(s\) to \(g\). The length of this path does not exceed \(1(3/2)\ast\pi\) times the length of the shortest path. Relations to experiments and lower bounds are discussed.