A computational complexity problem

Question

Consider $n$ arbitrary (but fixed) unit-norm vectors $\mathbf{x}_1,\ldots,\mathbf{x}_n$ in, say, $\mathbb{R}^d$. Let $\beta>0$ be fixed. For $\mathbf{y}\in\mathbb{R}^d$, define the binary quantities $b_i = \mathbf{1}(|\langle \mathbf{x}_i,\mathbf{y}\rangle| < \beta)\in\{0,1\}$, where $\mathbf{1}(\cdot)$ is the indicator function, and $|\langle \cdot,\cdot\rangle|$ is the absolute value of the inner product. Suppose that for any given $\mathbf{y}$ and $i\in\{1,\ldots,n\}$, calculating $b_i$ takes $O(1)$ time. Can calculating all $b_1,\ldots,b_n$ be accomplished in $o(n)$ time for any $\mathbf{y}$?