We consider the problem of on-line searching for the kernel of a unknown star-shaped polygon. In this motion planning problem, the robot starts from a point s inside a simple star-shaped polygon P , and aims to reach the kernel of P . The robot has no knowledge of P (apart from the fact that is a star-shaped polygon) but it is equipped with an on-board vision system that allows it to see its surrounding space. We prove that any strategy for this purpose in the worst case must traverse at least 1.515 times the shortest distance from s to the kernel of P . The lower bound is obtained by numerically computing a lower bound and then bounding the error of the computed solution algebraically. This improves over the best previously known lower bound of 1.44 by Lopez-Ortiz and Schuierer.
