Is there an efficient way of determining whether a given point $q$ is in the convex hull of a given finite set $S$ of points in $R^d$?

Yes. However, we need to be careful.

First we give a method that we do not recommend but many people use. This method computes an inequality representation $\{x\in R^d: A x \le b \}$ of $conv(S)$ where $A$ is some $m \times d$ matrix and $b$ is a $m$-vector. This is called the convex hull computation 2.10. Once the system $A x \le b$ is computed, it is easy to check whether $p$ satisfies the system or not.

In most cases, this method is too expensive, since the convex hull computation is very hard in general and impossible for large data. In fact, the number of inequalities in such a system $A x \le b$ is often exponential in $d$ and $n=\vert S\vert$. (This method might be of practical interests when we need to remove lots of redundant points in clouds of points in small dimensions, see 2.20.)

A standard method to check whether $q$ is in $conv(S)$ uses linear programming (LP) technique 4. An LP problem to be formulated for the question is the following. Let $S=\{p_1, p_2, \ldots, p_n \}$.

$$\begin{align*}\begin{array}{lll} \text{find} & q\\ \text{satisfying} & q = \sum_... ...= 1\\ & \lambda_i \ge 0 \text{ for all } i=1, \ldots, n. \end{array}\end{align*}$$ (3)

This problem has no objective function and such a problem is often called a linear feasibility problem. Although it might look simpler problem to solve, it is polynomially equivalent to the general LP. In fact, it is usually a good idea to set up an equivalent LP to solve it. More specifically, the problem (3) has a solution if and only if the following has no solution:

$$\begin{align*}\begin{array}{lll} \text{find} & z_0\in R \text{ and } z \in R^d\\... ...\le z_0 \text{ for all } i=1, \ldots, n\\ & z^T q > z_0. \end{array}\end{align*}$$ (4)

Geometrically, the meaning of this problem is simple. If it admits a solution $(z_0, z)$, then the set $H=\{x \in R^d: z^T x = z_0 \}$ is a hyperplane in $R^d$ separating the polytope $conv(S)$ from the inquiry point $q$. Thus the existence of the separation means the nonredundancy. Now, to actually solve the problem (4), we set up the LP:

$$\begin{align*}\begin{array}{lll} f^* = &\text{maximize} & z^T q - z_0\\ &\text{s... ...\text{ for all } i=1, \ldots, n\\ & & z^T q - z_0 \le 1. \end{array}\end{align*}$$ (5)

The last inequality is artificially added so that the LP has a bounded solution. It is easy to see that the point $q$ is non-redundant if and only if the optimal value $f^*$ of the LP (5) is (strictly) positive.