4

In a finite dimensional (think Euclidean) ambient space, let $S$ a compact, convex set and $x$ not in $S$. The two sets can be (weakly) separated, i.e. there exists a vector (normal) that defines a hyperplane separating the point and the set. In fact, there exists an entire (open) set of normals that separate the point and the set. How can one describe this set?

NilsD
  • 71

1 Answers1

2

Define \[ N = \{n \in S^{n-1}\,:\,\langle n, s-x\rangle < 0\;\text{for all $s \in S$} \}. \] The points $n \in N$ satisfy $\langle n, x \rangle > \langle n, s \rangle$ for all $s \in S$. In words, $x$ lies on the positive side of the hyperplane defined by $n$ and all $s \in S$ on the negative side (after a suitable translation in direction of $n$).

If you don't care about orientation take all vectors in $N \cup (-N)$.

Here's how I like to think about it:

After a translation we may assume that $x = 0$. Form the (closed convex) cone \[ C = \{\lambda s\,:\, \lambda \geq 0\}. \] Its polar cone is given by \[ C^{'} = \{y\,:\,\langle y, c\rangle \leq 0 \; \text{for all $c \in C$}\} = \{y\,:\,\langle y, s\rangle \leq 0 \; \text{for all $s \in S$}\}. \] The sought set of normals is then $N = S^{n-1} \cap \text{int}\,C'$, the intersection of the unit sphere with the interior of $C'$.

t.b.
  • 78,116
  • The set $N$ is open because $S$ is compact. Indeed, $s \mapsto \langle n, s - x \rangle$ attains its negative maximum, hence for all $n' \in S^{n-1}$ sufficiently close to $n$ we have $n' \in N$. – t.b. Jan 12 '11 at 01:29
  • thank you! I made a mistake in not specifying the definitions: when I write "normal", I do not imply "normalized vector". Apologies for the confusion. It also seems that, after seeing your answer, my question becomes rather trivial: define $p\in\mathbb{E}^n, p\neq 0$ the vector defining the separating hypeplane, i.e. $\sup_{x\in S}\langle p,x\rangle < \inf_{x\in B}\langle p,x\rangle$, with $B:={x^0}$ the point foreign to $S$. evidently, the set $P={p\in E^n\mid \langle p,x-x^0\rangle < 0 }$ is the interior of the polar (dual) cone of the set $S':=S-x^0$. – NilsD Jan 12 '11 at 11:58
  • @NilsD: What you seems right. Just remember: normal usually means orthogonal + normed. – t.b. Jan 12 '11 at 15:51