# A question on convex hull

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!

• 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. – Theo Bendit Jul 2 '15 at 18:45
• @JukesOnYou: $x$ is given. – joriki Jul 2 '15 at 18:49

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