5
$\begingroup$

I have $n$ points $x_1,\dots,x_n\in\Bbb R^d$, and I would like to check that some other point $y$ lies in their convex hull. How can I do this in some efficient way? I think that there was an algorithm based on checking the signs of pairwise inner products $x_i\cdot y$, however I was not able to find it.

$\endgroup$
4
$\begingroup$

$X = \{ x_1, \ldots, x_n \} \subset \mathbb{R}^d$. Then $$ \text{conv}(X) = \left\{ x \mid x = \sum_{i=1}^n \alpha_i \, x_i \wedge \alpha_i \ge 0 \wedge \sum_{i=1}^n \alpha_i = 1 \right\} $$ The test $$ y \in \text{conv}(X) $$ can be reformulated as linear program \begin{array}{rl} \min & c^\top \alpha \\ \text{w.r.t.} & A \alpha = y \\ & B \alpha = 1 \\ & \alpha \ge 0 \end{array} where $c \in \mathbb{R}^n$ can be an arbitrary cost vector, $A = (x_1, \ldots, x_n) \in \mathbb{R}^{d\times n}$, $y \in \mathbb{R}^d$ and $B = (1, \ldots, 1) \in \mathbb{R}^{1\times n}$.

If whatever solution $\alpha$ can be found, then the constraints are fulfilled, which are equivalent to having a feasible set of coefficients $\alpha$ for a convex combination of $y$.

This states that the test for general dimension $d$ is about as hard as solving a linear program of the above kind.

$\endgroup$
  • $\begingroup$ I hoped that this test should be a bit simpler as solving a (rather general looking) linear program. $\endgroup$ – Ulysses Nov 3 '15 at 14:33
  • 2
    $\begingroup$ See mathoverflow.net/questions/11508/… $\endgroup$ – mvw Nov 3 '15 at 14:35
  • 1
    $\begingroup$ Pretty wasteful if most of the points are inside the convex hull. Probably ought to get the convex hull first. $\endgroup$ – marty cohen Jul 25 '16 at 23:31
  • $\begingroup$ Just want to mention that if the author of the question was looking for a numerical implementation, there is a MATLAB one here. $\endgroup$ – ITA Jul 25 '16 at 23:34
  • $\begingroup$ @martycohen What would you do if you have the convex hull already? $\endgroup$ – Micha Wiedenmann Sep 20 '18 at 9:29
1
$\begingroup$

A point $P$ is outside the convex hull from a set $S$ iff the maximum angle $\{\angle aPb|a,b\in S\}$ is less than $\pi$ when read in one direction.

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