18
$\begingroup$

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$.

$\endgroup$
1
  • 4
    $\begingroup$ Btw it's not true that you can solve this in time poly in n and m. such an algorithm would be as trongly polynomial time algorithm for linear programming, which is as yet unknown. what is true is that you can solve it in polynomial time, but the running time involves terms relating to the bit complexity of the problem: en.wikipedia.org/wiki/Linear_programming#Algorithms $\endgroup$ Jan 12, 2010 at 8:38

3 Answers 3

15
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ (This is implicit in this answer, but this complexity result holds in two dimensions, and not in higher dimensions.) $\endgroup$ Oct 15, 2014 at 23:46
4
$\begingroup$

"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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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