Seperation of a Point and Convex Set

In summary, the conversation discusses the concept of separation of a point and a convex set. It is stated that there exists a point in the convex set that is closest to the given point. It is then shown that no point in the convex set lies on the perpendicular bisector of the line segment between the two points, and that this can be proved using geometry. The conversation then shifts to discussing the idea that a closed convex set is the intersection of all the closed half-planes that contain it, and it is concluded that this is true regardless of whether the half-planes are open or closed.
  • #1
e(ho0n3
1,357
0
[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?
 
Physics news on Phys.org
  • #2
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)
 
Last edited:
  • #3
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.
 
  • #4
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?
 
  • #5
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).
 
  • #6
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.
 
  • #7
just an edit to my post: I didn't meant an arbitrary intersection of half space, but rather the intersection of those half-space.
 

Related to Seperation of a Point and Convex Set

What is the definition of separation between a point and a convex set?

The separation between a point and a convex set refers to the minimum distance between the point and any point on the boundary of the convex set. In other words, it is the shortest distance from the point to the convex set.

How is the separation between a point and a convex set calculated?

The separation between a point and a convex set can be calculated using the Euclidean distance formula, which is the square root of the sum of the squared differences between the coordinates of the two points. Alternatively, it can also be calculated using the projection of the point onto the normal vector of the convex set's boundary.

What is the significance of the separation between a point and a convex set?

The separation between a point and a convex set is important in convex optimization and geometric programming. It is used to determine the feasibility and optimality of a convex optimization problem, and to find the optimal solution to the problem.

Can a point and a convex set be separated by more than one distance?

No, a point and a convex set can only be separated by one distance, which is the minimum distance between the point and the convex set's boundary. This distance is unique and cannot be exceeded by any other distance.

What are some applications of the separation between a point and a convex set?

The separation between a point and a convex set is used in various fields such as computer graphics, robotics, and computer vision. It is also used in machine learning for classification and clustering algorithms, and in mathematical optimization for solving constrained optimization problems.

Similar threads

Replies
9
Views
712
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
Replies
4
Views
954
  • Calculus and Beyond Homework Help
Replies
14
Views
612
  • Calculus and Beyond Homework Help
Replies
8
Views
597
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Back
Top