Shortest Distance between 2 convex sets

  • Thread starter TPks
  • Start date
  • #1
1
0
Hi, I hope someone can help me out with this problem:

Let set S be defined by (x in En :f(x) <=c}
f: En -> E1 is convex and differentiable and gradient of f(xo) is not 0 when f(x) = c. Let xo be a point such that f(xo) = c and let d = gradient at xo. Let lamda be any positive number and define x1 = xo+ lamda(d)
we know:
||x1-xo|| <= ||x1-x||
suppse we have 2 islands:
f(x,y) <= c1 and g(x,y) <= c2
where f and g are contibuously differentiable and strictly convex functions whose gradient vectors are non zero when f(x,y) = c1 and g(x,y)=c2

We need to build a bridge between the two islands of shortest possible length. Using the result of the theorem of separating hyperplane, devise a search technique to find the optimal bridge location.

Test your routine on:
f(x,y)= x^2 +2y^2, c1=1
g(x,y)= (x-4)^2 + (y-3)^2, c2 = 1
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,583
1,472
Did you get an answer for this? It sounds like you are to base you algorithm on hunting for a line segment (a "bridge") joining the surfaces of the two sets such that the separating hyperplane normal to that line segment is parallel to the tangent planes to the surface where the same line segment hits them. But whats the best way to search for such a line segment?

You could start with an arbitrary line segment. Look at the tangent planes at the ends of the line segment and determine which way to move the ends in order make the line segment more perpendicular to the tangent plane and then move the end of the current line a little way in that direction to get a new line segment.
 

Related Threads on Shortest Distance between 2 convex sets

  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
1
Views
2K
Replies
2
Views
664
  • Last Post
Replies
1
Views
2K
Replies
4
Views
4K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
3
Views
2K
Top