# Dynamic Ring Exploration with \((H,s)\) View +
## 4 Possibility Result and Upper Bounds of Exploration Time
** ExpOne\((t,v_{i})\) described in Algorithm 2 is an algorithm by which \(A\) explores at least one node or completes the exploration when \(A\) starts \(\textsc{ExpOne}(t,v_{i})\) from \(v_{i}\) at the \(t\)-th step under the assumption that \(v_{i}\) is the right or left extremity of \(V^{t}\). Note that in the following, when \(A\) executes \(\textsc{ExpOne}(t,v_{i})\), \(A\) is always on the right or left extremity of \(V^{t}\). When starting the algorithm, \(A\) first sees if \(v_{i}\) is the right extremity or the left one and stores the direction in \(dir\). Variables \(i^{\prime}\) and \(i^{\prime\prime}\) are used to remember the \(dir\) neighbor of \(v_{i}\) and the \(dir\) incident edge of \(v_{i}\) respectively, e.g., \(i^{\prime}=i+1\) (resp., \(i^{\prime}=i-1\)) if \(dir\) is _right_ (resp., _left_). Then, \(A\) stores \(\max(n-H,\lceil n/2\rceil)\) to \(S^{\prime}\) which is not larger than \(S\) and is used instead of \(S\) in the algorithm. After that, if \(e_{i^{\prime\prime}}\) appears by the \((t+S^{\prime}-1)\)-th step, \(A\) waits at \(v_{i}\) until \(e_{i^{\prime\prime}}\) appears and moves to \(v_{i^{\prime}}\) when \(e_{i^{\prime\prime}}\) appears. Otherwise, for each \(0\leq d\leq H-1\), \(A\) moves one hop to \(\overline{dir}\) at the \((t+d)\)-th step if \(e_{i^{\prime\prime}}\) is missing at the \((t+S^{\prime}-1+d)\)-th step in its view (Figure 2(a)). If \(A\) sees \(e_{i^{\prime\prime}}\) appear at the \((t+S^{\prime}-1+d)\)-th step in its view at the \((t+d)\)-th step, then \(A\) starts to move \(dir\) from the \((t+d)\)-th step, returns to \(v_{i}\), waits at \(v_{i}\) until \(e_{i^{\prime\prime}}\) appears, and reaches \(v_{i^{\prime}}\) through \(e_{i^{\prime\prime}}\) (Figure 2(b)). When \(d\) reaches \(H\), i.e., \(A\) moves \(H\) hops to \(\overline{dir}\) and \(e_{i^{\prime\prime}}\) is no longer included in the view of \(A\), \(A\) starts to keep moving to \(\overline{dir}\) until reaching \(v_{i^{\prime}}\) and the exploration finishes when reaching \(v_{i^{\prime}}\) (Figure 2(c)). ```
1:\(dir\leftarrow\mathit{Extremity}(t,v_{i})\)
2:ifdir is rightthen
3:\(i^{\prime}\gets i+1\), \(i^{\prime\prime}\gets i\)
4:else
5:\(i^{\prime}\gets i-1\), \(i^{\prime\prime}\gets i-1\)
6:\(d\gets 0\)
7:\(S^{\prime}\leftarrow\max(n-H,\lceil n/2\rceil)\)
8:while (\(d<H\)) do
9:if\(e_{i^{\prime\prime}}\) is always missing until the (\(t+d+S^{\prime}-1\))-th step then
10: Move one hop to \(\overline{dir}\)
11:\(d\gets d+1\)
12:else
13: Move \(d\) hops to \(dir\) (reach \(v_{i}\))
14: Wait for \(e_{i^{\prime\prime}}\) to appear and pass through \(e_{i^{\prime\prime}}\) as soon as it appears
15: Exit from the while loop
16:if(\(d\geq H\)) then
17: Move \(n-H-1\) hops to \(\overline{dir}\) (reach \(v_{i^{\prime}}\))
18: Wait until the (\(t+n\))-th step
```  
**Algorithm 2**ExpOne\((t,v_{i})\)  
**Lemma 3**. : _Suppose that at the \(t\)-th step, \(A\) exists at the right (resp., left) extremity, say \(v_{i}\), of \(V^{t}\) and starts \(\textsc{ExpOne}(t,v_{i})\). Then, \(A\) completes the exploration or reaches \(v_{i+1}\) (resp., \(v_{i-1}\)) by the (\(t+n\))-th step (the end  
Figure 3: The moves of \(A\) by \(\textsc{ExpOne}(t,v_{i})\) in the case where \(v_{i}\) is the right extremity. (**a**) Unless \(A\) sees \(e_{i}\) appear, \(A\) moves to left. (**b**) If \(A\) sees \(e_{i}\) appear before reaching \(v_{i-H}\), \(A\) starts to move to right and reaches \(v_{i+1}\). (**c**) If \(A\) reaches \(v_{i-H}\) without seeing \(e_{i}\) appear, \(A\) keeps moving to left until reaching \(v_{i+1}\) and finishes the exploration. of \(\textsc{ExpOne}(t,v_{i})\)). In addition to that, \(A\) exists on the right or left extremity of \(V^{t+n}\) at the (\(t+n\))-th step when the exploration has not been completed._  
Proof. : Without loss of generality, we assume \(v_{i}\) is the right extremity of \(V^{t}\). As in Algorithm 2, let \(S^{\prime}=\max(n-H,\lceil n/2\rceil)\).