The problem is NP hard. Here is a proof sketch.
The problem is to determine if there is a point $y$ with $\|y\|=1$ outside of the convex hull of given points $x_1,\dots, x_n$. Note that such point exists if and only if there is hyperplane at distance less than $1$ from the origin such that all points $x_1, \dots, x_n$ and $0$ lie on one side of the hyperplane (consider a hyperplane $\pi$ separating $x_1,\dots, x_n, 0$ and $y$).
So the problem can be stated as follows: is there $a\in {\mathbb R}^d$ s.t.
- $\langle a, x_i\rangle \leq 1$ (that is, all $x_i$ lie in the half-space $\{x: \langle a, x\rangle\leq 1\}$);
- $\|a\| > 1$.
Note that this problem is equivalent to the following well-known problem:
We are given a convex polytope $\cal P$, a positive definite matrix $A$ and a number $t$, find $x\in \cal P$ such that $x^T A x > t$. ($\cal P$ is described by a system of linear equations).
The optimization version of this problem is:
Quadratic Programming (Non-convex Linearly Constrained Quadratic Programming with Positive Definite Matrix). We are given a convex polytope $\cal P$ and and a positive definite matrix $A$, find $x\in \cal P$ that maximizes $x^T A x$. ($\cal P$ is described by a system of linear equations).
This problem is known to be NP hard.
It is even NP-hard to optimize $x^T A x$ when $\cal P$ is the unit cube $\{(b_1, \dots, b_d): -1\leq b_i \leq 1\}$ (this problem is known as Integer Quadratic Programming with Positive Definite Matrix). In particular, the MAX CUT problem is a special case of this problem. Let $G$ be a graph on $n$ vertices and $L$ be its Laplacian. Then $\max_{x\in\{\pm 1\}^n} x^T L x$ is equal to the size of the maximum cut in $G$ ($L$ is positive semi-definite, not positive definite, but this difference is not important; e.g. we can consider $L'=L+\varepsilon I$ with very small $\varepsilon$). The NP-hardness of MAX CUT was proved by Karp in
Richard M. Karp (1972). Reducibility Among Combinatorial Problems. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.