Deciding membership in a convex hull

Question

Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.

This can be done efficiently by linear programming (time polynomial in $n,m$) in the obvious way. I have two questions:

1. Is there a different (or more efficient algorithm) for this? If not, there ought to be a simple reduction from linear programming to the above problem as well. What is it?

2. Are there interesting families of instances for which the problem can be solved significantly faster than by means of linear programming, e.g., nearly linear time in $m+n$.

Answer 1

It isn't just that you can do the problem with linear programming. The reduction to linear programming actually shows that the convex hull problem is equivalent by dualization to the feasible-point problem in linear programming. In other words, you are asking whether there exist coefficients $\alpha_1,\ldots,\alpha_n \ge 0$ such that $$u = \alpha_1 v_1 + \alpha_2 v_2 + \cdots + \alpha_n v_n.$$ The vector of coefficients $\vec{\alpha}$ is a feasible point in a general linear programming problem, and you are asking whether a feasible point exists. Thus the problem can't be any harder or easier than linear programming.

Your second question then asks whether there are special cases of (the feasible point problem of) linear programming that are easier than the general case of linear programming. The answer is yes. For instance, the "quickhull" type algorithm that Steve Huntsman mentions performs well in any specific low dimension. It amounts to an algorithm for linear programming for the case that the coefficients are nonnegative and there are few equalities. You can also expect a faster algorithm (maybe even equivalent to quickhull) at the other extreme, when there are almost as many equalities as variables. And you can always think of new types of structured linear programming problems that are more convenient or faster, e.g. with a sparse matrix.

Answer 2

Quickhull uses divide and conquer a la quicksort. I believe its worst-case complexity is $O(n^2)$, but could be wrong.

Answer 3

"Are there interesting families of instances...nearly linear time..."

For the record it should be mentioned that if the points $v_1,\ldots,v_n \in \mathbb{R}^d$ are chosen randomly, under a variety of distributions and within a variety of regions (e.g., balls, hypercubes), then the number of vertices of the hull is $O(n^{1/3})$ in the plane and $O(\log^{d-1}n)$ in dimension $d$.

A recent reference, which cites many of the original papers is:

Sariel Har-Peled, "On the Expected Complexity of Random Convex Hulls." 2011. (arXiv abstract link).