algorithm - Find if a point is inside a convex hull for a set of points without computing the hull itself

Question

What is the simplest way to test if a point P is inside a convex hull formed by a set of points X?

I'd like an algorithm that works in a high-dimensional space (say, up to 40 dimensions) that doesn't explicitly compute the convex hull itself. Any ideas?

Answer 1

The problem can be solved by finding a feasible point of a Linear Program. If you're interested in the full details, as opposed to just plugging an LP into an existing solver, I'd recommend reading Chapter 11.4 in Boyd and Vandenberghe's excellent book on convex optimization.

Set A = (X[1] X[2] ... X[n]), that is, the first column is v1, the second v2, etc.

Solve the following LP problem,

minimize (over x): 1
s.t.     Ax = P
         x^T * [1] = 1
         x[i] >= 0  forall i

where

1. x^T is the transpose of x
2. [1] is the all-1 vector.

The problem has a solution iff the point is in the convex hull.