Finding the minimum distance between two curves

[Charles Link]

TL;DR

The problem is to compute the minimum distance between the two curves y=4-x^2 and y=(x-3)^2 in two dimensions.

The other day a friend of mine gave me the above problem which I found rather interesting. I was able to get a numerical solution. I'll post how I solved it later in the thread. Others may want to try it and see what they come up with.

 

[anuttarasammyak]

Square of the distance is
$$L^2=(y_1-y_2)^2+(x_1-x_2)^2=(4-x_1^2-(x_2-3)^2)^2+(x_1-x_2)^2$$
The condition of minimum is
$$\frac{\partial L^2}{\partial x_1}=\frac{\partial L^2}{\partial x_2}=0$$
Intersection of these two curves would give an answer.

 

[Charles Link]

@anuttarasammyak That's one part of what I did to solve it. Those two partial derivative expressions are really too clumsy to solve exactly. I used them though by getting an approximate $x$ for where the two $x$ values occur by first solving for the $x$ where the vertical distance is a minimum. That turns out to be at $x=3/2$.

I then let $x_1=3/2+ \Delta_1$ and $x_2=3/2+ \Delta_2$ and solved for $\Delta_ 1$ and $\Delta_2$ to first order using the two partial derivative expressions.

Others may want to try the calculation and/or have alternative ways of solving it, so I'm leaving just a summary of the solution rather than showing all of the details.

 

[anuttarasammyak]

continued from #2:
With the help of Wolfram I get one real solution. https://www.wolframalpha.com/input?i=Solve+(4-x^2-(y-3)^2)(-2x)+(x-y)=0+and++(4-x^2-(y-3)^2)2(y-3))+(x-y)=0.+

where $x=x_1,y=x_2$ Let us confirm it.
It is easily observed that the two curve formula coincide when $-x=y-3=-a$ thus a should satisfy
$$4a^3-6a-3=0$$
which derives all the solutions. Using real $a=2^{-1/3}+2^{-2/3}=1.42366...$.
The minimum distance is
$$L=\sqrt{4a^4-12a^2-12a+25}=\sqrt{-6a^2-9a+25}=\sqrt{19-12*2^{-1/3}-15*2^{-2/3}}=0.16182....$$
when $x_1=a, x_2=3-a$

I hope I commit no more careless mistakes.

 

[Charles Link]

@anuttarasammyak We are going to need to look over your two partial derivative expressions carefully, because your solution is incorrect and not even in the right ballpark. I got, doing it all by hand with no computer that $(x_1,y_1)=(1.43,1.96)$, and $(x_2,y_2)=(1.57,2.04)$ for a minimum distance of $L=0.16$. These are approximate coordinates, and only accurate to the two decimals.

Edit: and I looked over your partial derivative expressions=they look like they may be correct. The values for the real solution might also be correct, but I don't have a computer that can compute them. It looks like you did get $x_1=1.42366$ and $x_2=1.57634$ which is close enough to what I got that they are most likely correct and even exact in the form Wolfram has them. I think your error may be when you finished up.

Try computing $L$ again, but use $(x_1,y_1)$ and $(x_2,y_2)$. I don't know where your expression for $L$ using $a$ came from. Note: $L=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$.

With that one correction, I think everything else you did may be correct. :)

and I see you have now edited your post and made the correction. Very good=excellent. :)

 

[anuttarasammyak]

@anuttarasammyak We are going to need to look over your two partial derivative expressions carefully, because your solution is incorrect and not even in the right ballpark.

I am sorry for my careless mistakes on L. I corrected #4. It seems in good accord with your result.

 

[Charles Link]

I am sorry for my careless mistakes on L. I corrected #4. It seems in good accord with your result.

@anuttarasammyak Thank you very much for your solution above. It is excellent. <3 <3

 

[Charles Link]

@anuttarasammyak Perhaps you also noticed this already, but I find it interesting that with your exact solution, the slopes of the curves are precisely parallel, as they should be, at $x_1= a$ and $x_2=3-a$, with slopes of $-2 x_1 =-2a$ and $2(x_2-3)=-2a$.

Edit: I also believe that $(x_1,y_1),(x_2,y_2)$ and $(3/2,2)$ are co-linear with a slope of $1/(2a)$ of the line connecting them, making the line perpendicular to the two curves at the two points. I'll need to check this but I'm almost certain that it is the case. =and yes, I checked it, and it indeed is the case, as it needed to be. :)

( Note: $x=3/2$ is where the vertical distance is minimized, and $y=2$ is where the horizontal distance is minimized between the two curves. The point $(3/2,2)$ didn't need to be perfectly co-linear with the other two points, but I thought it might be, and yes, it is.)

 

[anuttarasammyak]

@anuttarasammyak Perhaps you also noticed this already, but I find it interesting that with your exact solution, the slopes of the curves are precisely parallel, as they should be, at x1=a and x2=3−a, with slopes of −2x1=−2a and 2(x2−3)=−2a.

After transformation of $X_2=3-x_2$ the two partial differential equations are
$$-2(4-x_1^2 -X_2^2)x_1+(x_1+X_2-3)=0$$
$$-2(4-x_1^2 -X_2^2)X_2+(x_1+X_2-3)=0$$
This pair of eqution is obviously symmetric between $x_1$ and $X_2$. This may help you to prove the features you find that have been not confirmed yet.

 

[Charles Link]

For the calculation with the slopes mentioned in post 8, we have $m=\frac{2-(4-a^2)}{3/2-a}=\frac{(3-a-3)^2-2}{3-a-3/2}$ and these are both $\frac{a^2-2}{3/2-a}=\frac{1}{2a}$ because of what @anuttarasammyak had previously mentioned in post 4 that comes from the first partial derivative expression that $4a^3-6a-3=0$.

Meanwhile the midpoint of the two points is readily computed to be $(x_m,y_m)=((a+3-a)/2, (4-a^2+(3-a-3)^2)/2)=(3/2,2)$.

 

[pasmith]

If $$L = (y_1(x_1) - y_2(x_2))^2 + (x_1 - x_2)^2$$ then the partial derivatives are $$\begin{split}
\frac{\partial L}{\partial x_1} &= 2(y_1 - y_2)y_1'(x_1) + 2 (x_1 - x_2) = 0 \\
\frac{\partial L}{\partial x_2} &= -2(y_1 - y_2)y_2'(x_2) - 2 (x_1 - x_2) = 0.\end{split}$$ Adding these gives $$
(y_1 - y_2) \left( y_1'(x_1) - y_2'(x_2)\right) = 0$$ whilst adding $y_2'(x_2)$ times the first and $y_1'(x_1)$ times the second gives $$
(x_1 - x_2) \left( y_1'(x_1) - y_2'(x_2)\right) = 0.$$ In each equation, one of other factor must vanish. For $y_1 = 4 - x^2$ and $y_2 = (x + 3)^2$ we know that $x_1 - x_2$ and $y_1 - y_2$ don't vanish simultaneously, so we must have $$y_1'(x_1) - y_2'(x_2) = -2(x_1 + x_2 + 3) = 0.$$ Eliminating one or other of $x_1$ and $x_2$ in either of the partial derivatives for $L$ then gives a cubic for the other, which can be solved analytically by standard methods.

 

[Charles Link]

Eliminating one or other of x1 and x2 in either of the partial derivatives for L then gives a cubic for the other, which can be solved analytically by standard methods.

Yes, sometime I'm going to need to try Vieta's substitution on this cubic and see if I can get the same answers that Wolfram got. :)

and perhaps @anuttarasammyak already identified the cubic in post 4 that needs to be solved. It may be simply solving $4a^3-6a-3=0$ to get the $x_1$.

and yes, I got Vieta's substitution to work on $a^3-\frac{3a}{2}-\frac{3}{4}=0$, so that $a=w+\frac{1}{2w}$. The solution is routine indeed to solve for $w^3$ and then $a$. :)

and I suggest the reader try this themselves. They will find they are able to solve this cubic for $a$ and get the same answer that Wolfram got in @anuttarasammyak post 4 above.

If we go to @anuttarasammyak post 9 and assume we have a solution where $x_1=X_2$, that solves it completely with what we did just above. and @pasmith showed in post 11 that $x_1+x_2-3=0$ where I think he got the sign wrong on the 3 but otherwise completely correct. :)

 

[Charles Link]

If $$L = (y_1(x_1) - y_2(x_2))^2 + (x_1 - x_2)^2$$ then the partial derivatives are $$\begin{split}
\frac{\partial L}{\partial x_1} &= 2(y_1 - y_2)y_1'(x_1) + 2 (x_1 - x_2) = 0 \\
\frac{\partial L}{\partial x_2} &= -2(y_1 - y_2)y_2'(x_2) - 2 (x_1 - x_2) = 0.\end{split}$$ Adding these gives $$
(y_1 - y_2) \left( y_1'(x_1) - y_2'(x_2)\right) = 0$$ whilst adding $y_2'(x_2)$ times the first and $y_1'(x_1)$ times the second gives $$
(x_1 - x_2) \left( y_1'(x_1) - y_2'(x_2)\right) = 0.$$ In each equation, one of other factor must vanish. For $y_1 = 4 - x^2$ and $y_2 = (x + 3)^2$ we know that $x_1 - x_2$ and $y_1 - y_2$ don't vanish simultaneously, so we must have $$y_1'(x_1) - y_2'(x_2) = -2(x_1 + x_2 + 3) = 0.$$ Eliminating one or other of $x_1$ and $x_2$ in either of the partial derivatives for $L$ then gives a cubic for the other, which can be solved analytically by standard methods.

@pasmith I think it should read $-2(x_1+x_2-3)=0$. Otherwise, yes, very good=excellent. :)

and I think I see where he got the wrong sign: Right before that he has $y_2=(x+3)^2$ where it should be a minus sign on the 3.

 

[Charles Link]

Just a couple additional comments: I thought I did pretty well by getting a numerical solution by writing out the partial derivative expressions and solving for $x_1$ and $x_2$ to first order about $x=3/2$. The exact solutions given by @anuttarasammyak and @pasmith are really a hundred times better though, thank you. <3 <3

 

[Gavran]

TL;DR: The problem is to compute the minimum distance between the two curves y=4-x^2 and y=(x-3)^2 in two dimensions.

The other day a friend of mine gave me the above problem which I found rather interesting. I was able to get a numerical solution. I'll post how I solved it later in the thread. Others may want to try it and see what they come up with.

Let $(x_1,y_1)$ be a point on the curve $f(x)=4-x^2$, which is the closest point on the curve $f(x)$ to the curve $g(x)=(x-3)^2$, and let $(x_1+a,y_1+b)$ be a point on the curve $g(x)=(x-3)^2$, which is the closest point on the curve $g(x)$ to the curve $f(x)$. That means that curves $y-b=4-(x-a)^2$ and $y=(x-3)^2$ intersect at only one point. The equation $b+4-(x-a)^2=(x-3)^2$ has only one solution, and its discriminant must be equal to zero. There is $2b+6a-a^2-1=0$.

The slope of $y=4-x^2$ in point $(x_1,y_1)$ is $-2x_1$ and it is equal to $-a/b$. Also, it is equal to the slope of $y=(x-3)^2$ in point $(x_1+a,y_1+b)$, and we have $-2x_1=2(x_1+a-3)$. From $-2x_1=-a/b$ and $-2x_1=2(x_1+a-3)$ we have $b=a/(3-a)$.

After substituting $b$ with $a/(3-a)$, the equation $2b+6a-a^2-1=0$ will be $a^3-9a^2+21a-3=0$. I can solve the equation $a^3-9a^2+21a-3=0$ without using a computer, only numerically. The computer gives me the result of $a=0,15267789$. $b=a/(3-a)$ implies that $b=0,05362157$.

The minimum distance is $\sqrt{a^2+b^2}=0,16182031$.

 

[Charles Link]

@Gavran Very good=Excellent. :)

You have an interesting approach where you translated the first curve by $(a,b)$ until it made contact with the second curve at $(x_1+a,y_1+b)$. (To get this to occur you set the discriminant to zero=very clever).

I checked over your calculations, and you are also in complete agreement with @anuttarasammyak , @pasmith , and Wolfram. You get $a^3-9a^2+21a-3=0$, but your $a=3-2x_1$. With that substitution, we once again have $4x_1^3-6x_1-3=0$ as first mentioned by @anuttarasammyak in post 4.

Good work and thank you. <3 <3

Edit: and I still recommend everyone try Vieta's substitution that I mentioned in post 12 to get the exact solution to this thing by hand. In the form the cubic is in, (first mentioned by @anuttarasammyak in post 4 ) without the $x^2$ term, it is ideal for Vieta's substitution. @Gavran 's cubic (with the $x$ distance between the two points as the variable) needs the translation to the $x_ 1$ term to get it in the form that is ideal for Vieta's substitution. (The $x^2$ term in the cubic needs to get eliminated). See https://mathworld.wolfram.com/VietasSubstitution.html

Edit 2: It may be worth mentioning that it may be a little tricky to get the signs correct in the translation of $y=4-x^2$ by $(a,b)$. I think it may help to put it in the form $f(x,y)=0$, and then the translated functional form is $f(x-a,y-b)=0$. This means we write it as $4-x^2-y=0$ and then the translated form is $4-(x-a)^2-(y-b)=0$.

 

[Charles Link]

Please see the two Edits added to post 16 above. I think they may be useful.

 

[DaveE]

My approach relied on symmetry and geometrical reasoning with just a tiny bit of calculus.

Since these two curves are translated and inverted versions of each other, I used a shifting transform to locate the origin at the midpoint between the maximum and minimum points on each curve. Because the transform is only shifting the curves, the spacing isn't changed, so there will be no need to invert the transform.

Because these curves are now symmetric about the origin, the minimum distance line segment must pass through the origin. It must also be normal to the curve surfaces. A circle centered at the origin and tangent to each curve will have a diameter equal to the minimum spacing. So if we locate the normal line from one curve that passes through the origin we can find the tangent point which will be the radius of that circle and half of the minimum spacing.

Edit: There's a sign error in the last cubic equation. It should be
$(2*uo-3)^3 - 12*uo + 24 = 0$ ⇒ $(2*uo-3)^3 - 6*(2*uo-3) + 6 = 0$

But the solution is still correct from there on.

 

[Charles Link]

@DaveE Excellent. In hindsight, your solution where you pointed out the inverted and translated symmetry of the two essentially identical parabolas is almost obvious, but I failed to recognize it. Thank you very much for your input. <3 <3

and your solution is in complete agreement with previous solutions by @anuttarasammyak , @pasmith , and @Gavran , and fundamentally very elegant. :)

 

[Gavran]

Edit: and I still recommend everyone try Vieta's substitution that I mentioned in post 12 to get the exact solution to this thing by hand. In the form the cubic is in, (first mentioned by @anuttarasammyak in post 4 ) without the $x^2$ term, it is ideal for Vieta's substitution. @Gavran 's cubic (with the $x$ distance between the two points as the variable) needs the translation to the $x_ 1$ term to get it in the form that is ideal for Vieta's substitution. (The $x^2$ term in the cubic needs to get eliminated). See https://mathworld.wolfram.com/VietasSubstitution.html

Analytical solution by using Vieta's substitution:

$\begin{align} &a^3-9a^2+21a-3=0\nonumber\\ &a^3-3a^23+3a9-27-3a9+27+21a-3=0\nonumber\\ &(a-3)^3-6a+24=0\nonumber\\ &(a-3)^3-6a+18-18+24=0\nonumber\\ &(a-3)^3-6(a-3)+6=0\nonumber\\ &a-3=w+\frac{6}{3w}=w+\frac{2}{w}\implies w^3+\frac{2^3}{w^3}+6=0\nonumber\\ &w^6+6w^3+2^3=0\nonumber\\ &w^3_{1,2}=\frac{-6\pm\sqrt{36-32}}{2}=-3\pm1\implies w_{1,2}=\sqrt[3]{-3\pm1}\nonumber\\ &a_{1,2}=3+\sqrt[3]{-3\pm1}+\frac{2}{\sqrt[3]{-3\pm1}}=\frac{\sqrt[3]{(-3\pm1)^2}+3\sqrt[3]{-3\pm1}+2}{\sqrt[3]{-3\pm1}}\nonumber\\ &a_1=\frac{\sqrt[3]{(-3+1)^2}+3\sqrt[3]{-3+1}+2}{\sqrt[3]{-3+1}}=-\frac{\sqrt[3]{4}-3\sqrt[3]{2}+2}{\sqrt[3]{2}}\nonumber\\ &a_2=\frac{\sqrt[3]{(-3-1)^2}+3\sqrt[3]{-3-1}+2}{\sqrt[3]{-3-1}}=-\frac{\sqrt[3]{16}-3\sqrt[3]{4}+2}{\sqrt[3]{4}}\nonumber\\ &a_2=-\frac{\sqrt[3]{2}\sqrt[3]{8}-3\sqrt[3]{2}\sqrt[3]{2}+\sqrt[3]{2}\sqrt[3]{4}}{\sqrt[3]{2}\sqrt[3]{2}}=-\frac{2-3\sqrt[3]{2}+\sqrt[3]{4}}{\sqrt[3]{2}}\nonumber\\ &a_1=a_2=a\nonumber\\ &b=\frac{a}{3-a}=-\frac{2-3\sqrt[3]{2}+\sqrt[3]{4}}{2+\sqrt[3]{4}}\nonumber\\ &\sqrt{a^2+b^2}=-(2-3\sqrt[3]{2}+\sqrt[3]{4})\sqrt{\frac{\sqrt[3]{4}+4+4\sqrt[3]{4}+\sqrt[3]{16}}{\sqrt[3]{4}(2+\sqrt[3]{4})^2}}\nonumber\\ &\sqrt{a^2+b^2}=-\frac{2-3\sqrt[3]{2}+\sqrt[3]{4}}{\sqrt[3]{2}(2+\sqrt[3]{4})}\sqrt{5\sqrt[3]{4}+4+2\sqrt[3]{2}}=0.1618203139\nonumber\\ \end{align}$

 

[Charles Link]

@Gavran Very good. I think your Vieta calculation above might have come from Wolfram. My apologies if I am incorrect.

When I recommended others to try it by hand above, (post 16), the version of the cubic I had, $x^3-\frac{3x}{2} -\frac{3}{4}=0$, (from post 12 above), didn't need the first translation, and I readily got that $w^3=\frac{1}{2}$ or $\frac{1}{4}$ , and finally $x_1 =w+\frac{1}{2 w }$, with $w$ being the real cube root of $\frac{1}{2}$ or $\frac{1}{4}$, and $x_1$ being the same whether the $\frac{1}{2}$ or $\frac{1}{4}$ solution is used.

What I did by hand only needed a few algebraic steps. :)