Batch membership testing for convex polyhedron specified in vertex representation

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?

• I see you're representing the convex polyhedron as the convex hull of a set of vertices (the vertex representation). If you convert this to half-space representation, the problem might be easier. I.e., convert to a a representation of the convex polyhedron as the intersection of a bunch of half-spaces, where each is specified by a linear inequality. Once it is in half-space representation, you can evaluate whether each of the linear inequalities is satisfied by the given point: if all inequalities are satisfied by the point, then the point is in the convex polyhedron; otherwise it isn't.
– D.W.
Aug 31, 2013 at 2:58
• (cont.) A warning, though: the half-space representation might be exponentially larger than the vertex representation, in the worst case. So, you might want to try this idea out on your real-world data to see whether it works in your situation or whether it goes exponential.
– D.W.
Aug 31, 2013 at 3:03

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.