Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite

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?

share|improve this question
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

1 Answer

up vote 2 down vote

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

share|improve this answer
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
@NilsD: What you seems right. Just remember: normal usually means orthogonal + normed. – t.b. Jan 12 '11 at 15:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.