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