How can one remove all interior points of $conv(S)$ from $S$ for large clouds $S$ of points in $R^d$?

The problem is formally known as the redundancy removal. Let $S$ be a set of $n$ points in $R^d$. We say a point $q \in S$ is redundant (for $conv(S)$) if $q \in conv(S-q)$. In short, redundant points are unnecessary to determine the convex hull $conv(S)$.

In principle, one can apply the linear programming (LP) method given in 2.19 to remove all redundant points. This amounts to solving $n$ LPs. While the time complexity of this pure LP method is polynomial and additional techniques given by [Cla94,OSS95] can reduce the size of LPs, this might end up in a very time consuming job for large $n$ (say $>1,000$).

There is a technique that might be useful to remove ``obviously redundant'' points quickly as a preprocessing. This works only in small dimensions (probably up to $100$?). Such a method picks up a few nonredundant point set $T=\{t_1, \ldots, t_k\}$ from $S$. Selecting nonredundant points can be done by picking points maximizing (or minimizing) any given linear function over $S$. When $k$ is small relative to $d$, say $d+2$ or $d+3$, the computation of $conv(T)$ is usually very easy with any standard convex hull algorithm. Thus we assume that an inequality system $A x \le b$ such that $conv(T)=\{x: A x \le b\}$ is given. It is easy to see that any point $q \in S-T$ satisfying the inequalities (i.e. $A q \le b$) is redundant. One can repeat the same procedure with a different set $T'$ of nonredundant points as long as it removes ``sufficient number'' of redundant points.