# How to check if a point is within a convex hull?

BACKGROUND

I'm working on a physics problem whereby I want to check whether a vector $$\vec{v}$$ of $$D \in \mathbb{N}$$ measurements $$v_d \in [-1, 1]$$, $$d \in \{1, \cdots, D\}$$ can result from the statistical averaging of $$K \in \mathbb{N}$$ possible measurement outcomes $$\vec{w}^{(k)}$$, $$k \in \{1, \cdots, K \}$$ where $$w_d^{(k)} \in \{-1, 1\}$$. (Note that unlike the elements of $$\vec{v}$$, those of $$\vec{w}^{(k)}$$ can only be $$\pm 1$$).

In other words, I want to check whether there exists a probability distribution $$\vec{p}$$ of dimension $$K$$ such that the following three conditions are satisfied, namely

$$$$v_d = \sum\limits_{k=1}^{K} p_k w^{(k)}_d,$$$$ $$\sum\limits_{k=1}^{k} p_k = 1$$, and $$p_k \in [0, 1]$$.

This is therefore an overcomplete problem if $$K > D$$, and, if I understand correctly, boils down to finding whether $$\vec{v}$$ lies within the convex hull formed by $$\{\vec{w}^{(k)}\}\mid_{k=1}^K$$.

QUESTION

How does one resolve the problem above, both analytically and algorithmically? Also, if it turns out that $$\vec{v}$$ can't be explained as a statistical mixture of $$\vec{w}^{(k)}$$'s, then can we quantify how far it is from being so, i.e., presumably, how far it lies from the convex hull?

To check containment of convex hull we usually have to compute the convex hull and then decide whether the new point is actually within this convex hull.

While there are many algorithms to compute the convex hull, checking the containment of a point within a convex hull is usually done using linear programming solver. (also see that it is roughly equivalent here).

To actually do this in practice I recommend relying on existing software (as understanding these algorithms and implementing them efficiently takes a lot of time). For example scipy has an arbitrary dimension convex hull algorithm built in, and requires only a few lines of code.

The only point that I see that might make your problem a little bit easier is the fact that your $$w^{(k)}$$ are the vertices of some hyper cube. (So a simple thing to do would first be checking whether $$v \in [-1,1]^D$$ so you can avoid doing the more expensive computations.)

• Thanks for pointing out that SciPy code, but can it actually return the combination $\vec{p}$ or does it just say whether $\vec{v}$ falls within the hull? Could it also return the shortest distance between the hull and $\vec{v}$? Apr 29, 2019 at 11:20
• You probably need some additional lines of code to get the combination, probably using a linear programming method. But you can directly infer whether it is inside the hull (see the link to SO) and the distance to the boundary is just a matter of iterating over all the faces of the convex hull and finding the minimal distance. Apr 29, 2019 at 12:37
• I played around with the code. I tried a certain value of $\vec{v}$ which the in_hull() function said to be inside the hull. I then tried a least square fit to compute $\vec{p}$ using NumPy. Half the elements of $\vec{p}$ turned out to be negative, which means they can't be interpreted as probabilities. So now I'm confused about the very definition of a convex hull. How can the coefficients be negative and yet the function says that it's inside the hull? Apr 29, 2019 at 19:36
• As the system is underdetermined a least squares fit will not necessarily find a valid solution to your problem as they usually try to minimize the norm of the solution in this case. You'd need a linear programming solver that let you include the constraints. Apr 29, 2019 at 20:02
• Earlier you said that the distance between the hull and $\vec{v}$ is just a matter of iterating over the faces of the hull and finding the minimum distance. Can one alternatively perform a constrained fitting of the parameters $\vec{p}$ and then take the Euclidean distance between the fitted $W \vec{p}$ and $\vec{v}$ (where $W$ is assembled from the $\vec{w}_k$s)? May 1, 2019 at 8:25