We consider a variant of shortest path problem within a simple polygon: Given a simple polygon, the robot at s having vision capability has to find path to an unknown target t. Since the location of t is unknown to the robot in advance, the path that robot travels may be longer than the shortest path from s to t. The question is whether there exists a path of the robot that is no α-times longer than the shortest path from s to t irrespective of the location of t. If the answer is positive, the path is called an α-competitive path.
In this thesis, we introduce and formally define the problem addressed above. We also present a linear-time algorithm to test whether a restricted rectilinear monotone polygon admits an α-competitive path. Finally, we give an $O(n^2)$-time algorithm to find an optimal competitive path within a restricted rectilinear monotone polygon, using the parametric searching technique.
