Seperation of a Point and Convex Set

[e(ho0n3]

[SOLVED] Seperation of a Point and Convex Set

Homework Statement

Let C be a closed convex set and let r be a point not in C. It is a fact that there is a point p in C with |r - p| l<= |r - q| for all q in C.

Let L be the perpendicular bisector of the line segment from r to p. Show that no point of C lies on L or in the half-plane, determined by L, which contains r.

2. The attempt at a solution
The point p happens to be the closest point in C to r. I can imagine how the point s in the middle of the line segment from r to p and some of the points near s on L could not be in C because then there would be a closer point to r in C than p. But what about points far away from s? I'm guessing the fact that C is closed and convex comes into play at this point, but how?

 

[quasar987]

I believe the idea you want to pursue is this:

Suppose there is a point x on L that is in C and consider the line L' joining x and p. Then all points of that line are in C because C is convex, and the orthogonal projection of r on that line is not p because if it were, the line L' would be parallel to L and hence never meet it.

(the orthogonal projection of r on L' is the point of L' that minimizes the distance btw L' and r. since L' is in C, we have a contradiction is that o.p. is not p)

 

[e(ho0n3]

That is a neat argument. If I imagine L', I can visualize how a point on it very close to p will be closer to r than p. This has now been reduced to a geometry problem which I think I can solve. Thanks a lot.

 

[e(ho0n3]

I have another problem: Show that each closed convex set is the intersection of all the closed half-planes that contain it.

For a point r not in C, I can always determine a line L as described in the previous posts which consequently determines an open half-plane that contains C but not r. If I do this for every point r not in C and take the intersection of these open half-planes, the intersection will not contain any of the points not in C. In other words, the intersection will just contain C.

The only problem here is that the half-planes are open. Perhaps the author meant to write open instead of closed. What do you think?

 

[quasar987]

I think an arbitrary intersection of half spaces will be closed, so no prob.

just like the intersection of all (1/n,infty) is [0,,infty).

 

[e(ho0n3]

I guess it doesn't really matter whether the half-planes containing C are open or closed because either way, they will exclude their corresponding r's and so the intersection will always end up having only points in C.

 

[quasar987]

just an edit to my post: I didn't meant an arbitrary intersection of half space, but rather the intersection of those half-space.