2
$\begingroup$

Let $a_1, a_2,\ldots, a_n$ be $n$ points in the $d$-dimensional Euclidean space. Suppose that $x$ is a point which does not belong to the convex hull of $a_1, a_2,\ldots, a_n$.

My question is, does there exist a vector $v$ such that $\langle v, x-a_i\rangle < 0$ for all $i$? My geometric intuitions tell me that it is true, but cannot find a rigorous proof. A rigorous proof will be appreciated!

$\endgroup$
  • 2
    $\begingroup$ Look up the Variation Inequality. Just choose $v$ to be $x - p$, where $p$ is a point of minimal distance from $x$ in the convex hull of the points. The variational inequality gives you the inequality you need. $\endgroup$ – Theo Bendit Jul 2 '15 at 18:45
  • 1
    $\begingroup$ @JukesOnYou: $x$ is given. $\endgroup$ – joriki Jul 2 '15 at 18:49
3
$\begingroup$

I figured I might as well expand on my comment. Let $C$ be the convex hull of the given points (or indeed, any closed convex set). Choose $p$ to be a point of minimal distance from $x$ in $C$ (in fact, it will be unique).

Suppose, for the sake of contradiction, there exists some $c \in C$ such that $\langle x - p, c - p \rangle > 0$. Suppose $\lambda \in \mathbb{R}$, and let $f(\lambda) = \|\lambda c + (1 - \lambda)p - x\|^2$. Then, since $p$ is of minimal distance from $x$, and for $\lambda \in [0, 1]$, $\lambda c + (1 - \lambda)p \in C$, $f$, considered over the domain $[0, 1]$, should therefore attain a minimum at $\lambda = 0$. We have \begin{align*} f(\lambda) &= \|\lambda(x - c) + (1 - \lambda)(x - p)\|^2 \\ &= \lambda^2 \|x - c\|^2 + (1 - \lambda)^2 \|x - p\|^2 + 2\lambda (1 - \lambda) \langle x - p, x - c \rangle \\ f'(\lambda)&= 2\lambda\|x - c\|^2 - 2(1 - \lambda)\|x - p\|^2 + (2 - 4\lambda) \langle x - p, x - c \rangle \\ f'(0) &= 2 \langle x - p, x - c \rangle - 2\|x - p\|^2 \\ &= -2 \langle x - p, c - p \rangle < 0 \end{align*} But then $f$ is decreasing to the right of $\lambda = 0$, which implies it cannot have its minimum at $\lambda = 0$. This is a contradiction, implying that $\langle x - p, c - p \rangle \le 0$ for any $c \in C$.

Let $v = p - x$. Then, $$\langle v, x - a_i \rangle = \langle p - x, p - a_i \rangle - \|p - x\|^2 < 0,$$ from the result proven. The strict inequality comes from the fact that $x$ is not in $C$ and thus cannot equal $p$.

$\endgroup$
1
$\begingroup$

Let $y$ be the point on the hull closest to $x$. Then $v=x-y$ works.

The intuition is that all points in the hull are on the same side with respect to the hyperplane passing through $x$ and orthogonal to $x-y$.

$\endgroup$
  • $\begingroup$ This is exactly what Theo Bendit suggested. I only saw his comment now. $\endgroup$ – lhf Jul 2 '15 at 19:04

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.