# Dynamic Ring Exploration with \((H,s)\) View +
## 4 Possibility Result and Upper Bounds of Exploration Time
We first show the lemma for the case \(e_{i}\) appears by the (\(t+d+S^{\prime}-1\))-th step in \(A\)'s view at the (\(t+d\))-th step for \(0\leq d\leq H-1\). For \(d=0\), \(A\) can clearly reach \(v_{i+1}\) by the (\(t+S^{\prime}-1\))-th step. For \(1\leq d\leq H-1\), when \(A\) sees \(e_{i}\) appear for the first time at the (\(t+d+S^{\prime}-1\))-th step in its view at the (\(t+d\))-th step, \(e_{i}\) must appear at the (\(t+d+S^{\prime}-1\))-th step and be missing at the \(t^{\prime}\)-th step for \(t+d\leq t^{\prime}\leq t+d+S^{\prime}-2\) by the construction. This means that all the other links than \(e_{i}\) are present at the \(t^{\prime}\)-th step (\(t+d\leq t^{\prime}\leq t+d+S^{\prime}-2\)), and thus \(A\) can move for \(S^{\prime}-1\) steps from \(v_{i-d}\) to right without interference by missing links until reaching \(v_{i}\). Since \(d\leq H-1\) and \(H\leq S^{\prime}\), \(A\) always reaches \(v_{i}\) by the (\(t+d+S^{\prime}-1\))-th step at which \(e_{i}\) appears. Then, \(A\) reaches \(v_{i+1}\) as soon as \(e_{i}\) appears. Since \(A\) moves at most \(H-1\) hops to left, \(e_{i}\) appears \(S^{\prime}\) steps after \(A\) starts to move to right, and \(H-1+S^{\prime}\leq n\) from \(S^{\prime}=\max(n-H,\lceil n/2\rceil)\), \(A\) reaches \(v_{i+1}\) through \(e_{i}\) by the (\(t+n\))-th step. We then show for the other case, i.e., \(A\) reaches \(v_{i-H}\) at the (\(t+H\))-th step. When this happens, \(e_{i}\) must be deleted for at least \(S^{\prime}-1\) steps from the (\(t+H\))-th step and all the other links than \(e_{i}\) are present in the \(S^{\prime}-1\) steps. Thus, \(A\) can move for \(S^{\prime}-1\geq n-H-1\) steps from \(v_{i-H}\) to left without interference by missing links until reaching \(v_{i+1}\) since \(S^{\prime}=\max(n-H,\lceil n/2\rceil)\). Since \(H+n-H-1=n-1\), \(A\) reaches \(v_{i+1}\) after \(n-H-1\) steps, i.e., at the (\(t+n-1\))-th step, and the exploration is completed at the same time. **Exploration algorithm. ** Algorithm 3 describes the exploration algorithm. Let \(S^{\prime\prime}=\min(S,n-1)\). The algorithm repeats \(\textsc{ExpH}(t,v_{i})\) for \(\lfloor(S^{\prime\prime}+1-H^{\prime})/H^{\prime}\rfloor\) times (lines 2-6) and \(\textsc{ExpOne}(t,v_{i})\) for \(n-H^{\prime}\lfloor(S^{\prime\prime}+1-H^{\prime})/H^{\prime}\rfloor-1\) times (lines 7-13). We call the part repeating \(\textsc{ExpH}(t,v_{i})\) (lines 2-6) _the first part_ and the part repeating \(\textsc{ExpOne}(t,v_{i})\) _the second part_ (lines 7-13). In the first part, \(H^{\prime}\lfloor(S^{\prime\prime}+1-H^{\prime})/H^{\prime}\rfloor+1\) nodes are explored and, in the second part, the remaining \(n-H^{\prime}\lfloor(S^{\prime\prime}+1-H^{\prime})/H^{\prime}\rfloor-1\) nodes are explored. ```
1:\(S^{\prime\prime}\leftarrow\min(S,n-1)\)
2:\(p\gets 1\) //starting the first part
3:while (\(p\leq\lfloor(S^{\prime\prime}+1-H^{\prime})/H^{\prime}\rfloor\)) do
4: Let \(t\) be the current step and \(v_{i}\) be the current node
5:\(\textsc{ExpH}(t,v_{i})\)
6:\(p\gets p+1\)
7:\(p\gets 1\) //starting the second part
8:while (\(p\leq n-H^{\prime}\cdot\lfloor(S^{\prime\prime}+1-H^{\prime})/H^{\prime} \rfloor-1\)) do
9: Let \(t\) be the current step and \(v_{i}\) be the current node
10:\(\textsc{ExpOne}(t,v_{i})\)
11:if Exploration is completed then
12: Exit from the while loop
13:\(p\gets p+1\)
```  
**Algorithm 3** Exploration algorithm for \(H+S\geq n\)  
Theorem 1.: _For \(H+S\geq n\) and \(S\geq\lceil n/2\rceil\), the exploration time of \(1\)-interval connected rings by a single agent with the (\(H,S\)) view is upper-bounded by \(O(n^{2}/H+nH)\) if \(2H^{\prime}-1\leq S\) or otherwise it is upper-bounded by \(O(n^{2})\)._Proof. : It suffices to show that \(A\) with the \((H,S)\) view completes exploration within \(O(n^{2}/H+nH)\) steps if \(2H^{\prime}-1\leq S\) or otherwise \(O(n^{2})\) steps by executing Algorithm 3 when \(H+S\geq n\) and \(S\geq\lceil n/2\rceil\). We first consider the case where \(2H^{\prime}-1\leq S\).