 \log n)$ time.  Our search algorithm is a binary tree search. Whenever we reach node $\textbf{v}$, if $D(\text{rep}_v,q) < D_{\text{near}}$ set $\text{best}_q =\text{rep}_v$ and $D_{\text{near}} = D(\text{rep}_v,q)$ as our current nearest neighbor and nearest neighbor distance respectively. Our branching criterion is that if $D (\text{rep}_v, q) < (0 + \frac{t}{0}) r_v$, we continue search in $\mathbf{v_{\text{in}}}$, else we continue the search in $\mathbf{v_{\text{out}}}$. Since the depth of the tree is $O(\log n)$ by Lemma \[ringsep\], this process will take $O(\log n)$ time.  