Asymptotics

As we have seen in Theorem 1, there is a lower bound of 2 on the competitive ratio for all strategies and large $d$. In the following we will show that for large $d$, there is a matching upper bound on our circle strategy presented in Section 3.3, proving it to be asymptotically optimal. For limited physical distances, it shows that even for arbitrarily small scan times, there is a relatively simple strategy that achieves the optimal ratio of 2.

Our proof of the upper bound proceeds as follows. Let us assume that we are given some fixed $\varepsilon>0$. We then proceed to show that for $c=2+\varepsilon$, the recursion presented in Section 3.3 does not collapse before the corner is reached, if the diameter $d$ of the semi-circle is large enough.

In proving the lower bound stated in Theorem 1, we have used the obvious fact that the length $d_n$ of the optimal path cannot exceed the length of the robot's path. Now we are turning this argument around: The robot's path to position $n$ does not exceed the length of the circular arc leading from the start to position $n$. As this arc is not much longer than $d_n$, the length of the chord from the start to $n$, if the diameter $d$ of the circle is large enough. More precisely, we use the following.

Claim (i) can be shown by the same technique as in the proof of Theorem 1. In order to prove claim (ii), let $a$ and $c$ denote the maximum lengths of an arc and its chord in a circle of diameter $d$ satisfying $a \leq b + \varepsilon^2$. Let $2\beta$ denote the angle of the arc, as seen from the center, so that $a=d \beta$ and $c=d \sin \beta$ hold. The maximum arc satisfying the condition is of length $a=d \beta_d$ where $\beta_d$ is the solution of the equation $\beta_d - \sin \beta_d = \varepsilon^2 /d$. In the equivalent expression

$$d \beta_d \left(1 - \frac{\sin \beta_d}{\beta_d} \right) = \varepsilon^2$$

the fraction tends to one, so $a=d \beta_d$ must be unbounded. $\qedsymbol$

These facts will now be used in providing a lower bound for the first steps along the semi-circle, aiming for a competitive ratio of $c=2+\varepsilon$.

Using Lemma 1 we can choose $d_0$ large enough that

$$\sum_{i=1}^{n} x_i \leq d_n + \varepsilon^2$$

holds for all $n \leq N$ if $d \geq d_0$. Now we proceed by induction. For $x_1:=(1+\varepsilon)$ the claim is fulfilled. For $n=2$ we observe that $d_1 = x_1$ holds, so the recursive formula (1) yields

$$x_2 = (2+\varepsilon) (1+d_1) - 2 - x_1$$

$$= (2+\varepsilon)^2 -3 -\varepsilon \geq 1+3\varepsilon.$$

Now assume the claim was true for $x_1,\ldots,x_{n-1}$, where $n\geq 3$, and let $d_{n-1}$ be the $(n-1)$st chord, arising by connecting the start point with the $(n-1)$st scan point. The induction hypothesis implies

$$\sum_{i=1}^j x_i \geq \sum_{i=1}^j \left( 1+\left(2^{i}-1\right)\varepsilon\right) = j + (2^{j+1}-j-2)\varepsilon.$$

From the recursion we obtain

$$x_n=(2+\varepsilon)(1+d_{n-1})-n-\left(\sum_{i=1}^{n-1} x_{i}\right).$$

As $d \geq d_0$, we have $d_{n-1}\geq \left(\sum_{i=1}^{n-1} x_{i}\right)-\varepsilon^2$ for $n \leq N$. As $n\geq 3$, we get

$$x_n \geq (2+\varepsilon)\left(1+\left(\sum_{i=1}^{n-1} x_{i}\right)-\varepsilon^2\right) - n- \left(\sum_{i=1}^{n-1} x_{i}\right)$$

$$= (1+\varepsilon)\left(\sum_{i=1}^{n-1} x_i \right) + (2+\varepsilon)(1-\varepsilon^2)-n$$

$$= 1+(2^n-1)\varepsilon + (2^n -n-3-\varepsilon) \varepsilon^2$$

$$\geq 1+(2^n-1)\varepsilon. \hspace*{0.3cm}\qed$$

Under the assumptions of Lemma 2 we can now prove the following.

We may assume that

$$x_n\geq 1+\left(2^{n}-1\right)\varepsilon$$

holds for $n \leq N$. If $N$ is large enough and $n\geq N/2$, we get

$$x_{n}\geq 1+ \left(\frac{10}{\varepsilon}-1\right)\varepsilon \geq 10.$$

Thus,

$$\sum_{i=1}^{N-1} x_i\geq \sum_{i=N/2}^{N-1} x_i\geq 5N,$$

as claimed. $\qedsymbol$

To conclude the proof, we consider a diameter $d$ large enough for Lemma 3 to hold, so we have a lower bound of 5 on the average size for the first $N$ steps. This suffices to show that all following steps are at least of length 5.

Again we proceed by induction and consider

$$x_n=(2+\varepsilon)(1+d_{n-1})-n-\left(\sum_{i=1}^{n-1} x_{i}\right).$$

As all $x_i$ are lengths of chords of the semi-circle with diameter $d$, we have

$$d_{n-1}\geq \frac{2}{\pi}\sum_{i=1}^{n-1} x_i.$$

By a similar argument as before, we get

$$x_n \geq (2+\varepsilon)\left(1+\frac{2}{\pi} \left(\sum_{i=1}^{n-1} x_{i}\right)\right)- n - \left(\sum_{i=1}^{n-1} x_{i}\right)$$

$$\geq \left(\frac{4}{\pi}-1\right)\left(\sum_{i=1}^{n-1} x_{i}\right) - n+2$$

$$\geq \left(\frac{4}{\pi}-1\right) 5n - n+2 \geq 5,$$

since $n\geq 12$, as claimed. $\qedsymbol$

With the help of these lemmas, we get

The preceding Lemmas 2, 3, 4 show that for any large enough $d$, the sequence will consist of step lengths that are all at least 5. This implies that the sequence will reach the corner in a finite number of steps, showing that a competitive factor of $(2+\varepsilon)$ can be reached. $\qedsymbol$

ARRAY(0x9264af0)ARRAY(0x9264af0)ARRAY(0x9264af0)ARRAY(0x9264af0)