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

2 Answers 2

7
$\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$
6
  • $\begingroup$ I hoped that this test should be a bit simpler as solving a (rather general looking) linear program. $\endgroup$
    – Ulysses
    Commented Nov 3, 2015 at 14:33
  • 2
    $\begingroup$ See mathoverflow.net/questions/11508/… $\endgroup$
    – mvw
    Commented Nov 3, 2015 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$ Commented Jul 25, 2016 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
    Commented Jul 25, 2016 at 23:34
  • $\begingroup$ @martycohen What would you do if you have the convex hull already? $\endgroup$ Commented Sep 20, 2018 at 9:29
3
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .