I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the convex shape. Currently I just use an open source linear programming solver for each point independently with a constant objective function.
However this is quite slow even in 100 dimensions. Is there a way to use the fact that all the query points are known in advance to speed the process up?
Instead of testing each point individually whether it is contained in the convex polyhedron, you should search for a supporting hyperplane of the polyhedron which separates the point from the polyhedron. If a supporting hyperplane does not exists, you know that the point is contained in the polyhedron. Otherwise, the supporting hyperplane helps you to separate additional points from the polyhedron. This is similar to the idea of D.W. but here you only enumerate a smaller number of supporting hyperplanes which is sufficient to separate all outer points.
Here are the details: Let $V$ be a matrix whose columns are the vertices $\mathbf{v}_1,\dots,\mathbf{v}_k$ of the polyhedron $\mathbf{P}$. The test points are denoted by $\mathbf{w}_1,\dots,\mathbf{w}_l$. A hyperplane $\{\mathbf{x}\mid \mathbf{n}^T\mathbf{x} = \lambda\}$ separates $\mathbf{P}$ and some point $\mathbf{w}_j$ if and only if $\mathbf{n}^T\mathbf{v}_i \leq \lambda$ for all $i=1,\dots,k$ and there is some positive $\epsilon>0$ with $\mathbf{n}^T\mathbf{w}_j \geq \lambda+\epsilon$. Assume, such an $\epsilon$ exists, then the conditions above are equivalent to $\frac{1}{\epsilon}\mathbf{n}^T\mathbf{v}_i - \frac{1}{\epsilon}\lambda \leq 0$ for all $i=1,\dots,k$ and $\frac{1}{\epsilon}\mathbf{n}^T\mathbf{w}_j - \frac{1}{\epsilon}\lambda \geq 1$. Substituting $\frac{1}{\epsilon}\mathbf{n}$ by $\tilde{\mathbf{n}}$ and $\frac{1}{\epsilon}\lambda$ by $\tilde{\lambda}$ yields the system of linear inequalities $$V\tilde{\mathbf{n}} - \mathbf{1}\tilde{\lambda} \leq 0,\quad \mathbf{w}_j^T\tilde{\mathbf{n}} - \tilde{\lambda} \geq 1$$ where $\mathbf{1}$ is the vector whose coefficients are all $1$. Hence, the linear program $$\mbox{minimize } \lambda \mbox{ subject to } V\mathbf{n} - \mathbf{1}\lambda \leq 0,\ \mathbf{w}_j^T\mathbf{n} - \lambda \geq 1$$ is either infeasible and $\mathbf{w}_j$ is contained in $\mathbf{P}$ or its optimal solution $(\lambda, \mathbf{n})$ provides a separating hyperplane, which is indeed a supporting hyperplane of $\mathbf{P}$. Each remaining point $\mathbf{w}_i$ with $\mathbf{n}^T\mathbf{w}_i > \lambda$ is also not contained in $\mathbf{P}$ and can be removed from the test set.
