4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Aug 31 '13 at 2:58
  • $\begingroup$ (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. $\endgroup$ – D.W. Aug 31 '13 at 3:03
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.