Test if point is in convex hull of $n$ points I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$, and I would like to check that some other point $y$ lies in their convex hull. How can I do this in some efficient way? I think that there was an algorithm based on checking the signs of pairwise inner products $x_i\cdot y$, however I was not able to find it.
 A: $X = \{ x_1, \ldots, x_n \} \subset \mathbb{R}^d$. Then
$$
\text{conv}(X) = 
\left\{
x \mid x = 
\sum_{i=1}^n \alpha_i \, x_i \wedge 
\alpha_i \ge 0 \wedge
\sum_{i=1}^n \alpha_i = 1 
\right\}
$$
The test
$$
y \in \text{conv}(X)
$$ 
can be reformulated as linear program
\begin{array}{rl}
\min & c^\top \alpha \\
\text{w.r.t.} & A \alpha = y \\
& B \alpha = 1 \\
& \alpha \ge 0 
\end{array}
where $c \in \mathbb{R}^n$ can be an arbitrary cost vector, $A = (x_1, \ldots, x_n) \in \mathbb{R}^{d\times n}$, $y \in \mathbb{R}^d$ and
$B = (1, \ldots, 1) \in \mathbb{R}^{1\times n}$.
If whatever solution $\alpha$ can be found, then the constraints are fulfilled, which are equivalent to having a feasible set of coefficients $\alpha$ for a convex combination of $y$.
This states that the test for general dimension $d$ is about as hard as solving a linear program of the above kind.
A: A point $P$ is outside the convex hull from a set $S$ iff the maximum angle $\{\angle aPb|a,b\in S\}$ is less than $\pi$ when read in one direction.
