Basic Observations

First, we introduce some notation that will be used throughout this section.

Let us assume that the corner that hides the object is at distance $d$ from the start. Let $x_i$ denote the distance the robot travels in the $i-$th step, i.e., on its way from position $i-1$ to position $i$, from which the $i-$th scan will be taken. If the object was hidden infinitesimally behind position $i$, the optimal solution would go perpendicularly to the line $L_i$ that runs from the corner through position $i$, and then take one scan from there. Let $d_i$ denote the length of this line segment and observe that it meets $L_i$ at a point that lies on the semi-circle spanned by the start and the corner. Then the optimum cost to detect the object would be $1+d_i$, whereas the robot would only see the object at position $i+1$, having accumulated a cost of

$$i+1 + \sum_{j=1}^{i+1} x_j.$$

Now suppose that $c$ is the smallest competitive ratio that can be achieved in this setting. By local optimality, for any scan position, the ratio of the solution achieved and the optimal solution must be equal to $c$. Therefore,

$$x_{i+1} = c(1+d_i) - (i+1) - \sum_{j=1}^i x_j$$ (1)

must hold for $i=1,2,\ldots$ In particular, we have $x_1 = c-1$ for the first step.