# Describing a set of normals

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?

-
Perhaps this will help en.wikipedia.org/wiki/Separating_axis_theorem – PEV Jan 12 '11 at 0:32
@Trevor: thank you. It seems to me that it is a re-iteration of the question on the "primal" space. – NilsD Jan 12 '11 at 11:25

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)$.
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'$.
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 1: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