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

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

• I hoped that this test should be a bit simpler as solving a (rather general looking) linear program. – Ulysses Nov 3 '15 at 14:33
• – mvw Nov 3 '15 at 14:35
• Pretty wasteful if most of the points are inside the convex hull. Probably ought to get the convex hull first. – marty cohen Jul 25 '16 at 23:31
• Just want to mention that if the author of the question was looking for a numerical implementation, there is a MATLAB one here. – ITA Jul 25 '16 at 23:34
• @martycohen What would you do if you have the convex hull already? – Micha Wiedenmann Sep 20 '18 at 9:29

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.