4
$\begingroup$

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?

  • 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 1

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

  • 0
    @NilsD: What you seems right. Just remember: normal usually means orthogonal + normed.2011-01-12