# Dynamic Ring Exploration with \((H,s)\) View +
## 3 Impossibility Result  
We show an impossibility result in this section. Specifically, we show that the exploration is impossible when \(H+S<n\) or \(S<\lceil n/2\rceil\) holds. Lemma 1: _If \(H+S<n\) or \(S<\lceil n/2\rceil\), a deterministic single agent with the \((H,S)\) view cannot explore \(1\)-interval connected rings._Proof. : We first consider the condition \(S<\lceil n/2\rceil\). We assume \(H=\lceil n/2\rceil\). It suffices to show that the exploration is impossible when \(S=\lceil n/2\rceil-1\). We assume for contradiction, that there is an algorithm by which \(A\) can explore any ring under any link scheduling when \(S=\lceil n/2\rceil-1\). Since \(A\) can explore the ring, \(A\) starting from \(v_{0}\) eventually reaches \(v_{n-1}\) (no matter whether the exploration is completed or not). The adversary decides a link scheduling so that \(e_{n-1}\) (resp., \(e_{n-2}\)) is missing when \(A\) exists on \(v_{0}\) (resp., \(v_{n-2}\)). The adversary first keeps showing a link scheduling where \(e_{n-1}\) is kept deleted for \(S\) steps from the current step until \(A\) moves to \(v_{n-\lceil n/2\rceil}\). If \(A\) does not move to \(v_{n-\lceil n/2\rceil}\) and stays \(v_{l}\) for \(0\leq i<n-\lceil n/2\rceil\), \(e_{n-1}\) is kept deleted and \(A\) cannot reach \(v_{n-1}\) (\(A\) must pass through \(e_{n-1}\) or \(e_{n-\lceil n/2\rceil-1}\) to reach \(v_{n-1}\) from \(v_{0}\)), which is a contradiction. Thus, \(A\) eventually reaches \(v_{n-\lceil n/2\rceil}\) at some step, say \(t\). Then, the adversary deletes \(e_{n-2}\) from the \((t+S-1)\)-th step (the \((t+\lceil n/2\rceil-2)\)-th step) until \(A\) moves to \(v_{n-\lceil n/2\rceil-1}\). By the scheduling, since \(A\) reaches \(v_{n-2}\) at earliest at the \((t+n-2-(n-\lceil n/2\rceil))\)-th step (the \((t+\lceil n/2\rceil-2)\)-th step) from \(v_{n-\lceil n/2\rceil}\), \(e_{n-2}\) starts to disappear when (or before) \(A\) reaches \(v_{n-2}\) and keeps disappearing unless \(A\) moves to \(v_{n-\lceil n/2\rceil-1}\). Thus, if \(A\) does not move to \(v_{n-\lceil n/2\rceil-1}\), \(A\) cannot reaches \(v_{n-1}\). This is a contradiction. This means that \(A\) moves to \(v_{n-\lceil n/2\rceil-1}\) after the \(t\)-th step. However, by the similar way, the adversary can prevent \(A\) from reaching \(v_{n-1}\). This is a contradiction. Hence, when \(S<\lceil n/2\rceil\), a single agent cannot explore \(1\)-interval connected rings. Secondly, we consider the condition \(H+S<n\) and \(S\geq\lceil n/2\rceil\). It is sufficient to show that \(A\) cannot explore the ring when \(S=n-H-1\) for \(1\leq H\leq\lfloor n/2\rfloor-1\) since \(H<\lfloor n/2\rfloor\) from the conditions. Again, we assume for contradiction, that there is an algorithm by which \(A\) can explore any ring under any link scheduling. Since \(A\) can explore the ring, \(A\) starting from \(v_{0}\) eventually reaches \(v_{n-1}\) (no matter whether the exploration is completed or not). The adversary first keeps showing a link scheduling where \(e_{n-1}\) is kept deleted for \(S\) steps from the current step until \(A\) moves to \(v_{H}\). If \(A\) does not move to \(v_{H}\) and stays at \(v_{l}\) for \(0\leq i\leq H-1\), \(e_{n-1}\) is kept deleted and \(A\) cannot reach \(v_{n-1}\), which is a contradiction. Thus, \(A\) eventually reaches \(v_{H}\) at some step, say \(t\). After step \(t\), depending on whether \(A\) reaches \(v_{H-1}\) before \(v_{n-H-1}\) or not, the missing link is decided (Figure 1). Note that since \(H\leq\lfloor n/2\rfloor-1\), \((n-H-1)-(H-1)\geq 2\) and there exists a node \(v_{i}\) such that \(H\leq i\leq n-H-2\). Moreover, \(A\) can see neither \(e_{n-1}\) nor \(e_{n-2}\) in its view when existing at \(v_{i}\) for \(H\leq i\leq n-H-2\). If \(A\) reaches \(v_{H-1}\) before \(v_{n-H-1}\), the adversary keeps deleting \(e_{n-1}\). By the link scheduling, unless \(A\) decides to reach \(v_{n-H-1}\) from \(v_{H}\), \(e_{n-1}\) is kept deleted and \(A\) cannot reach \(v_{n-1}\), which is a contradiction. This means that \(A\) eventually reaches \(v_{n-H-1}\).