# Dynamic Ring Exploration with \((H,s)\) View +
## 4 Possibility Result and Upper Bounds of Exploration Time  
In this section, we prove the exploration is possible when \(H+S\geq n\) and \(S\geq\lceil n/2\rceil\) by giving an exploration algorithm by a single agent. In the following, we use \(H^{\prime}=\min(H,\lfloor n/2\rfloor)\). The algorithm also gives upper bounds of the exploration time, \(O(n^{2}/H+nH)\) if \(2H^{\prime}-1\leq S\) or otherwise \(O(n^{2})\). Note that \(S\geq H\) since \(S\geq\lceil n/2\rceil\) and \(H\leq\lceil n/2\rceil\). We first introduce two operations \(\textsc{ExpH}(t,v_{i})\) and \(\textsc{ExpOne}(t,v_{i})\) that are used as building blocks to construct the exploration algorithm. In the algorithms, \(\mathit{Extremity}(t,v)\) is a function which returns _right_ if \(v\) is the right extremity of \(V^{t}\), _left_ if \(v\) is the left extremity, or otherwise _nil_. Variable _dir_ is used to store the direction and \(\overline{dir}\) denotes the other direction (e.g., if _dir_ is _right_, \(\overline{dir}\) is _left_). ExpH.\(\textsc{ExpH}(t,v_{i})\) described in Algorithm 1 is an algorithm by which \(A\) explores \(H^{\prime}\) nodes when \(A\) starts \(\textsc{ExpH}(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}\) and \(2H^{\prime}+|V^{t}|-1\leq\min(S+1,n)\). Note that in the following, when \(A\) executes \(\textsc{ExpH}(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 _right_ if \(v_{i}\) is the right extremity or otherwise _left_ in _dir_. If \(A\) can move \(H^{\prime}\) hops to _dir_ by the \((t+2H^{\prime}+|V^{t}|-2)\)-th step according to the view, \(A\) does so (Figure 1(b)). Otherwise, \(A\) moves \(|V^{t}|-1+H^{\prime}\) hops to \(\overline{dir}\) (Figure 1(c)). Notice that \(A\) can decide this condition because \(H^{\prime}\leq H\) and \(2H^{\prime}+|V^{t}|-2\leq S\). ```
1:\(dir\leftarrow\mathit{Extremity}(t,v_{i})\)
2:if\(A\) can move \(H^{\prime}\) hops to \(dir\) by the \((t+2H^{\prime}+|V^{t}|-2)\)-th step then
3: Move \(H^{\prime}\) hops to \(dir\)
4:else
5: Move \(|V^{t}|-1+H^{\prime}\) hops to \(\overline{dir}\)
6:Wait until the \((t+2H^{\prime}+|V^{t}|-2)\)-th step
```  
**Algorithm 1**\(\textsc{ExpH}(t,v_{i})\)  
**Lemma 2**. : _Suppose that at the \(t\)-th step, \(A\) exists at the right or left extremity, say \(v_{i}\), of \(V^{t}\) and starts \(\textsc{ExpH}(t,v_{i})\). If \(2H^{\prime}+|V^{t}|-1\leq\min(S+1,n)\), \(A\) explores \(H^{\prime}\) nodes by the \(t^{\prime}\)-th step (the end of \(\textsc{ExpH}(t,v_{i})\)) and exists on the right or left extremity of \(V^{t}\) at the \(t^{\prime}\)-th step where \(t^{\prime}=t+2H^{\prime}+|V^{t}|-2\)._  
Proof. : Without loss of generality, we assume \(v_{i}\) is the right extremity of \(V^{t}\). Let \(m=|V^{t}|\), \(E_{r}=\{e_{i},e_{i+1}\),..., \(e_{i+H^{\prime}-2}\), \(e_{i+H^{\prime}-1}\}\), and \(E_{l}=\{e_{i-H^{\prime}-m+1},e_{i-H^{\prime}-m+2},\)..., \(e_{i-2}\), \(e_{i-1}\}\). Note that since \(|E_{r}|+|E_{l}|=2H^{\prime}+m-1\) and \(2H^{\prime}+m-1\leq n\), \(E_{r}\cap E_{l}=\emptyset\). Now, consider the move of \(A\). Since \(2H^{\prime}+m-1\leq S+1\), i.e., \(2H^{\prime}+m-2\leq S\), \(A\) can see whether it can move \(H^{\prime}\) hops to right by the \((t+2H^{\prime}+m-2)\)-th step or not. If \(A\) can, \(A\) moves \(H^{\prime}\) hops to right and thus the lemma holds. Otherwise, \(A\) can move at most \(H^{\prime}-1\) hops to right by the \((t+2H^{\prime}+m-2)\)-th step, which means during the \(2H^{\prime}+m-2\) steps, there exists at least \(2H^{\prime}+m-2-(H^{\prime}-1)=H^{\prime}+m-1\) steps at each of which one of the links in \(E_{r}\) is missing. Since at most one link is missing at each step and \(E_{r}\cap E_{l}=\emptyset\), every link in \(E_{l}\) exists at each of the \(H^{\prime}+m-1\) steps. Thus, \(A\) succeeds to move \(H^{\prime}+m-1\) hops to left and the lemma holds. **ExpOne.