Searching and on-line recognition of star-shaped polygons
We study the problem of on-line searching for a target inside a polygon. In particular, we propose a strategy for finding a target of unknown location in a star-shaped polygon with a competitive ratio of 11.52. We also provide a lower bound of 9 for the competitive ratio of searching in a star-shaped polygon which is close to the upper bound. A similar task is the on-line recognition of a star-shaped polygon P. Here, the robot travels on a path that allows it to decide whether P is star-shaped or not. We present a strategy with a competitive ratio of 28.85 and give a lower bound of root82 for this problem. (C) 2003 Elsevier Science (USA). All rights reserved.
star-shaped polygons on-line searching competitive ratio algorithmic foundations of robotics motion planning