Take the 2-minute tour ×
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.

I want to show the following:

Let $A,B \subseteq \mathbb{R}^n$ disjoint, nonempty, closed and convex sets. Then there exists a $h \in \mathbb{R}^n$, such that $A$ and $B$ gets separated in the following way: $$ \langle b, h \rangle \le \langle a, h \rangle \quad \forall a \in A, b \in B. $$ I have the following proof: Consider $C := B - A$, which is convex too. Because $A$ and $B$ are disjoint, it must be that $0 \notin C$. (*) Then there exists a $h$ such that $\langle c, h \rangle \le 0$ for all $c \in C$ or $\langle c, h \rangle \ge 0$ for all $c \in C$. WLOG let $\langle c, h \rangle \le 0$, then $\langle b - a, h \rangle \le 0$, which means $\langle b, h \rangle - \langle a, h \rangle \le 0$, i.e. $$\langle b, h \rangle \le \langle a, h \rangle.$$

But (*) uses the fact that: For every convex set $X$ and a point $u \notin X$, there exists a $h$ such that $\langle u, h \rangle = 0$ and $\langle x, h \rangle \le 0$ for all $x \in X$ or $\langle x, h \rangle \ge 0$ for all $x \in X$.

Which I feel is geometrically true because the Elements $h$ could be identified with hyperplanes, but I am not sure how to proof this?

share|improve this question
    
Do you understand how to identify an element $h \in \mathbb{R}^n$ and a constant $c$ with a hyperplane? It refers to the set of points $x\in \mathbb{R}^n$ such that $< h, x> = c$. For each point, the length of the projection onto vector $h$ will be of length $c/ ||h||$. –  Calvin Lin Jan 4 '13 at 18:33
    
that i know, btw you mean the length of the projection of every point $p$ will be $c / ||p||$. –  Stefan Jan 4 '13 at 18:36
    
The length of the projection of a point $p$ onto the vector $h$ will be $c/||h||$. This comes from the equation of a plane, say $x+2y+3z = 4$. This can be expressed by the dot product as $(x, y, z) \cdot (1, 2, 3) = 4$. –  Calvin Lin Jan 4 '13 at 18:43
    
Well, $A$ and $B$ are closed, but does it follow that $C = B - A$ is closed? Why do you need closed sets anyway? –  GEdgar Jan 4 '13 at 18:50
    
but $c / ||h||$ does not depend on the point, so it would be the same for every point? –  Stefan Jan 4 '13 at 19:06
add comment

1 Answer

Your comment (*) is a bit off, so I'll go ahead without it.

Firstly, if there exists an $h$ such that $\langle c, h \rangle \le 0$ for all $c\in C$, then $-h$ satisfies $\langle c, -h \rangle \ge 0$ for all $c \in C$. So the two cases are equivalent, and you only need to solve either.

Now, your question is essentially reduced to building a hyperplane through the origin for which your convex set $X$ falls entirely on one side. A good guess would be to take the plane perpendicular to some point of the set (which would then become your $h$), but which? Try taking $h$ to be the closest point of $X$ to the origin. Try proving that if there was some point of $X$ on the other side of the hyperplane, then convexity would force another point to be closer to the origin than $h$.

share|improve this answer
    
The first paragraph is falsely stated (even in the question). It holds with a constant $c$ replacing $0$, which is the separating hyperplane theorem. We can't guarantee that the hyperplane will pass through the origin, since the origin could be contained within one of the sets. –  Calvin Lin Jan 4 '13 at 20:11
    
@CalvinLin: but we're only applying it to $C = A - B$, which does not contain the origin. In any case, isn't it easy enough to just translate co-ordinates, and put the origin wherever you like? –  Ben Millwood Jan 4 '13 at 21:33
    
I guess I'm confused about the 'uses the fact' then. Let's say that the convex set $X$ is the unit disc, and $u=(0,2)$ is not in $X$. What would $h$ be then? I do not see why that statement is true. More generally, even if you want $0 \not \in X$, take an interior point $I \in X$, take $u = I/n$, with $n$ large enough (since $0 \not \in X$. Then any vector $h$ such that $<u,h>=0$ is perpendicular to $u$, and the (neighbourhood of $I$) dot product $h$ has range a neighborhood of 0 –  Calvin Lin Jan 4 '13 at 22:04
    
@CalvinLin: okay, I concede that the question itself is confused. I responded to what I assumed was meant, instead of what was actually written – I didn't prove (*) but instead a related idea that, well, is actually true, and leads to the desired result. –  Ben Millwood Jan 4 '13 at 22:15
    
@CalvinLin: I see what you mean, now, I've edited some of my answer. –  Ben Millwood Jan 4 '13 at 22:19
add comment

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.