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
-
0Perhaps this will help http://en.wikipedia.org/wiki/Separating_axis_theorem – 2011-01-12
-
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'$.
-
0The 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$. – 2011-01-12
-
0thank 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$. – 2011-01-12
-
0@NilsD: What you seems right. Just remember: normal usually means orthogonal + normed. – 2011-01-12