Test if point is in convex hull of $n$ points

Question

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.

Answer 1

$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.

Answer 2

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.