Search code examples
optimizationdistancegeometrycurves

finding a minimum distance

I need to find a point or points on the given circle (or curve) which minimizes d0+d1? the radius and center of the curve are (0,0) and 'r' respectively and the coordinates of points A and B are known. Let say A=(x1,y1) and B=(x1,-y1) and r> sqrt(x1^2+y1^2) . C is unknown point of the circle which should minimize the length d0+d1 d0 - the distance between A to C on the circle d1- the distance between B to C on the circle

point C moves along the circle. I need to find a point or points on the given circle (or curve) which minimizes d0+d1?

Solution

  • The general case is very complicated, but the special situation

    A=(x1,y1) and B=(x1,-y1) and r > sqrt(x1^2+y1^2)

    with a circle whose centre is the origin has enough symmetries to make the solution at least in some circumstances accessible. I'm assuming A ≠ B, (equivalently y1 ≠ 0), otherwise the problem is trivial for a circle.

    Let dist(P,Q) be the Euclidean distance between the points P and Q. The (closed) line segment connecting A and B is the locus of points P with

    dist(P,A) + dist(P,B) = dist(A,B)

    For D > dist(A,B), the locus of points with

    f(P) = dist(P,A) + dist(P,B) = D

    is an ellipse E(D) whose foci are A and B. Let P be a point on the circle and D = f(P).

    • If the tangents to the circle and to the ellipse E(D) in the point P don't coincide, P is neither a local minimum nor a local maximum of f restricted to the circle.
    • If the tangents coincide, and the curvature of the circle is larger than the curvature of E(D) in P, then P is an isolated local maximum of f restricted to the circle.
    • If the tangents coincide, and the curvature of the circle is smaller than the curvature of E(D) in P, then P is an isolated local minimum of f restricted to the circle.
    • If the tangents coincide and the curvature of the circle is equal to the curvature of E(D) in P, then
      • P is an isolated local minimum of f restricted to the circle if dist(P,A) = dist(P,B),
      • P is neither a local maximum nor a local minimum of f restricted to the circle otherwise.

    First, if x1 = 0, it is easily seen (in case it is not geometrically obvious) that the points on the circle minimising f are the points with x-coordinate 0, i.e. P1 = (0,r) and P2 = (0,-r). [That would even be true if r² ≤ x1² + y1².]

    Now, suppose x1 ≠ 0, without loss of generality x1 > 0. Then it is obvious that a point P = (x,y) on the circle minimising f must have x > x1. By the symmetry of the situation, the point R = (r,0) must either be a local minimum or a local maximum of f restricted to the circle.

    Computing the behaviour of f near R, one finds that R is a local minimum if and only if

    r ≥ (x1² + y1²) / x1

    Since R is a point of smallest curvature of E(f(R)) (and the tangents in R to E(f(R)) and the circle coincide), R is then also the global minimum.

    If r < (x1² + y1²) / x1, then R is a local maximum of f restricted to the circle. Then f has two global minima on the circle, with the same x-coordinate. Unfortunately, I don't have a nice formula to compute them, so I can't offer a better way than an iterative search.