# Closest distance between two quadratic curves

I'm having trouble with the following problem :

"find the closest distance between $x^2+4y^2=4$ and $xy=4$"

I tried to solve using the properties of ellipse and hyperbola, but the relatively tilted axes makes it hard, i think. I also thought about using a circle that has its center on $xy=4$ and is tangent to $x^2+4y^2=4$, but the method seems to make equations too messy.

curves generated at https://www.desmos.com/

I'd really appreciate some hints, and i'm also curious if the problem can be generalized to finding the closest distance between two quadratic curves.

-
There are various ways to set this problem up, but I'm not sure any formulation of the problem is easily solved. – Jason Zimba Mar 29 '14 at 13:54

My try : I selected two arbitrary points $(x_e,y_e)$ and $(x_h,y_h)$ and I computed the distance which I say to be minimum.

$y_e$ can be eliminated (expressed as a function of $x_e$ since the point is along the ellipse).

$y_h$ can be eliminated (expressed as a function of $x_h$ since the point is along the hyperbole).

Now, I want that the derivatives of the distance with respect to both $x_e$ and $x_h$ be equal to zero. This leads to a terrible system of two equations for the two unknowns $x_e$ and $x_h$ but, fortunately, we only need to consider the first quadrant because of the symmetry. Moreover, complex solutions can be discarded.

I cannot get an analytical solution but using numerical methods, the only solution corresponds to $(1.62723,0.581406)$ along the ellipse and $(2.39098,1.67296)$ along the hyperbole.

Using Lagrange multipliers (then $6$ variables) took me to the same result.

The results were later confirmed building a contour plot of the distance as a function of parameters $x_e$ and $x_h$.

The problem can reduce to a single variable (say $x_e$) problem, eliminating $x_h$ as a function of $x_e$ from one of the derivative of the distance with respect to the variables. What is then left is to solve the remaining derivative for $x_e$ (the advantage of keeping $x_e$ as the single variable of the problem is that it is bounded between $0$ and $2$).

So, the problem is now reduced to the solution of a single equation for a single unknown. This works and leads to identical results. Newton methods works quite well except if the iterations start at $x_e=0$ or $x_e=2$ which correspond to infinite branches. But, for example, starting iterations at $x_e=1$, the successive iterates are $1.32085$, $1.57018$, $1.62728$, $1.62723$.

This approach could be used for finding the closest distance between two conics.

-
Can you kindly articulate more about using the Lagrange multipliers? Also, is an analytical solution anavailable mathematically? If so, is it possible to find the length of the shortest distance? – Chanhee Jeong Mar 30 '14 at 6:01
@Chanhee Jeong. Let us say that we keep as variables $(x_e,y_e,x_h,y_h)$. So the distance is a function of this four unknowns. Now, we must introduce the two equality constraints corresponding to the fact that $(x_e,y_e)$ is along the ellipse and that $(x_h,y_h)$ is along the hyperbole. So the total objective function is the distance augmented by two Lagrange coefficients, each of them multiplying one equality constraint. This is a classical procedure (just google for "Lagrange multipliers") – Claude Leibovici Mar 30 '14 at 6:55
@Chanhee Jeong. In my opinion, there is no analytical solution to this problem. – Claude Leibovici Mar 30 '14 at 6:59
@Chanhee Jeong. I think that the simplest is one equation for $x_e$ as variable. Newton work fine. See what I added to my answer. – Claude Leibovici Mar 30 '14 at 7:31
@claudeleibovici yes, I think it requires root of a high degree polynomial. Not surprised to see the use of numerical methods here. – Jason Zimba Mar 30 '14 at 20:45

Since both functions are very smooth, I think this MIGHT work.

First simply take the derivatives of the two functions. Then solve for when the normal lines of the derivatives of the two functions are identical (both in slope and y-intercept). The resulting normal line should also be the shortest line between the two curves.

Justification (by contradiction): take a case where the shortest line intersects two points for which the normals are not "equal". This means that the normals intersect at some coordinate, and also form an angle (and triangle with the "shortest" line).

Now, since our functions are very smooth and nice, as we move along the points of our functions, the normals must be becoming more and more similar (in slope) (i.e. their angle increases). Also, as long as our tangents intersect, the functions must be "edging" closer together.

So we continue going down our functions until when the tangents/derivatives stop intersecting, i.e. where they are parallel. This is also the point where the normals are the same line (with same c and m). Since we have been "Edging" closer, the resulting line contacting the 2 functions must be shorter than the original "shortest line". So in fact, the initial line was not the shortest line; the "normal" is.

Important: there are infinitely many normals for the 2 function which will have the same slope, but only 1 with the same c (y-intercept).This 1 line can be found by checking the tangents' equations.

Extra (showing the actual equations):

If I have not made a mistake in the math, one should eventually end up having to solve the following system of equations

Note: x and y are just arbitrary symbols (x represents the x-coordinate of the desired point on the ellipse and y represents the x-coordinate of the desired point on the hyperbola).

-
Is this argument about arbitrary 'smooth and nice' curves? Its method does solve my problem(thank you), but i'm afraid there could be some cases where there are two or more normals overlapping. But of course, the shortest distance can be found among the normals I guess – Chanhee Jeong Mar 30 '14 at 5:59
What you said is true, this method is case specific, but nevertheless good as it is pretty straight forward. I just said the thing about "smoothness" because the method's justification relies on the premise that the derivatives gradually and continually shift. I should have added to my answer that the geometry of the studied objects will determine whether this method is optimal. – Just_a_fool Mar 30 '14 at 12:09
@Just_a_fool. I tried your approach and it works very well for the same results. May I confess that your solution is more elegant that mine (which basically uses brute force) ? Cheers. – Claude Leibovici Mar 30 '14 at 15:00
@Just_a_fool Only to check my understanding, you still need a numerical analysis in the end, correct? Your method is also the one that I had tried...in pursuing it, I came to a point where a numerical approach was required. – Jason Zimba Mar 31 '14 at 12:44
Starting Newton at y=3/2, the first iterate is $$5+\frac{5348}{3 \left(3 \sqrt{6} 7^{3/4}-560\right)}=1.62614$$ which is almost the solution – Claude Leibovici Apr 1 '14 at 6:02