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?
Describing a set of normals
-
0@Trevor: thank you. It seems to me that it is a re-iteration of the question on the "primal" space. – 2011-01-12
1 Answers
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'.
-
0@NilsD: What you seems right. Just remember: normal usually means orthogonal + normed. – 2011-01-12