Post Reply 
Brain Teaser - Minimum distance between two curves
11-18-2015, 04:35 PM (This post was last modified: 11-18-2015 04:41 PM by CR Haeger.)
Post: #1
Brain Teaser - Minimum distance between two curves
Finding the point on a curve closest to a fixed point off the curve seems to be fairly straightforward and often can be solved by hand. Finding the points on each of two curves which are closest seems to be a bit more involved.

Problem: What points on each of the two curves f(x) = x^2+1 and g(x) = āˆš(x) are closest to each other?

   

I worked this one mainly by hand, then used the HP Prime CAS when things got messy (and they did for me). Can you solve this by hand, by CAS, programming or other methods?
Find all posts by this user
Quote this message in a reply
11-18-2015, 05:50 PM (This post was last modified: 11-18-2015 06:25 PM by Vtile.)
Post: #2
RE: Brain Teaser - Minimum distance between two curves
."Piece of cake" with Sensored. I have theary with arithmetics, but francly I have more important things to do atm. than reviving this particular thing to my head. Coffee break is over. Tongue

Edit, Sensored

Edit2. If I'm not terribly mistaken the points are: x=0.34368 and x=0.39685 .. But I might just be totally wrong, the still in learning with 50g doesn't make it any easier. OK Couldn't resist, back to work.
Edit3. Yep, it is wrong, would have been too easy.
Find all posts by this user
Quote this message in a reply
11-18-2015, 06:18 PM
Post: #3
RE: Brain Teaser - Minimum distance between two curves
Sorry, CR Haeger, my maths isn't up to it, but I'm interested in the answer.

Sad that such a superior mathematician as Vtile can't find the time to advise you on this, for him, trivial problem.
Find all posts by this user
Quote this message in a reply
11-18-2015, 06:24 PM (This post was last modified: 11-18-2015 06:27 PM by Vtile.)
Post: #4
RE: Brain Teaser - Minimum distance between two curves
(11-18-2015 06:18 PM)Gerald H Wrote:  Sorry, CR Haeger, my maths isn't up to it, but I'm interested in the answer.

Sad that such a superior mathematician as Vtile can't find the time to advise you on this, for him, trivial problem.

I'm not a great mathematician, but graphical solution with somekind of accuracy is easy with one tool that pathfinders use.
Find all posts by this user
Quote this message in a reply
11-18-2015, 06:40 PM
Post: #5
RE: Brain Teaser - Minimum distance between two curves
(11-18-2015 04:35 PM)CR Haeger Wrote:  Finding the point on a curve closest to a fixed point off the curve seems to be fairly straightforward and often can be solved by hand. Finding the points on each of two curves which are closest seems to be a bit more involved.

Problem: What points on each of the two curves f(x) = x^2+1 and g(x) = āˆš(x) are closest to each other?

x = cube root (1/16)

Hint: must be tangent point of both curves

-Jonathan
Visit this user's website Find all posts by this user
Quote this message in a reply
11-18-2015, 07:06 PM (This post was last modified: 11-18-2015 08:03 PM by CR Haeger.)
Post: #6
RE: Brain Teaser - Minimum distance between two curves
(11-18-2015 06:40 PM)Jonathan Cameron Wrote:  
(11-18-2015 04:35 PM)CR Haeger Wrote:  Finding the point on a curve closest to a fixed point off the curve seems to be fairly straightforward and often can be solved by hand. Finding the points on each of two curves which are closest seems to be a bit more involved.

Problem: What points on each of the two curves f(x) = x^2+1 and g(x) = āˆš(x) are closest to each other?

x = cube root (1/16)

Hint: must be tangent point of both curves

-Jonathan

You are close but I think you (correctly) solved for the x where the difference between f(x) and g(x) values are minimized. The x you provided is between the two x values that are the solution.

Hint: a line should be normal to both curves.
Find all posts by this user
Quote this message in a reply
11-18-2015, 07:23 PM (This post was last modified: 11-18-2015 10:11 PM by Vtile.)
Post: #7
RE: Brain Teaser - Minimum distance between two curves
The my millimeterpaper and compas gives solution of 0.35 and 0.57 with scale of 10. Interesting, I definedly need to make some rereading of my old mathbooks.

Interesting teaser indeed. The tangent way is not solid even at this case, ie. points x=1/4 and x=1/2 have same angle and because of that the angle of normals are same in multitude of places, but like you CR Haeger do mention normal which is line and is normal for both curves and have same zero for both curves is the solution. Another solution ofcourse would be a circle which center point is one or another of the curves and have radious where there is only one common point for another curve. Now I should just figure out how to construct a function for it, no idea. Big Grin

Hmm... since derivative of given function is angle of tangent and we know that angle of normal is -(a^-1) so the function for a normal of given function is therefore -1/f'(x) and we know normal of both function is the same we would assume that we find the right solution where both normal functions intersects, but since we also know that there is more than one solution for angle of tangents so there is more than one solution for angle of normals we need more glue, so I need to yet vacuumclean my dustbin to figure out how the line function at given point were build. Oh this is fun in bizarre way, have been missing it kind of. Tongue
Find all posts by this user
Quote this message in a reply
11-18-2015, 10:19 PM
Post: #8
RE: Brain Teaser - Minimum distance between two curves
xf = 0.331694745644, xg = 0.568071280353, distance = 0.427592353667

Just defining the normals and forcing them to be equal for both curves.
You get a 5-th degree polynomial that I solved numerically..

Cheers, Werner

41CVā€ ,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
11-18-2015, 11:47 PM
Post: #9
RE: Brain Teaser - Minimum distance between two curves
(11-18-2015 07:06 PM)CR Haeger Wrote:  
(11-18-2015 06:40 PM)Jonathan Cameron Wrote:  x = cube root (1/16)

Hint: must be tangent point of both curves

-Jonathan

You are close but I think you (correctly) solved for the x where the difference between f(x) and g(x) values are minimized. The x you provided is between the two x values that are the solution.

Hint: a line should be normal to both curves.

Oops! I made an implicit assumption that the slopes would be equal at the same x. When I got rid of that assumption, I get a gory polynomial -- which I have not solved yet...
Visit this user's website Find all posts by this user
Quote this message in a reply
11-19-2015, 12:30 AM (This post was last modified: 11-19-2015 04:51 PM by CR Haeger.)
Post: #10
RE: Brain Teaser - Minimum distance between two curves
(11-18-2015 10:19 PM)Werner Wrote:  xf = 0.331694745644, xg = 0.568071280353, distance = 0.427592353667

Just defining the normals and forcing them to be equal for both curves.
You get a 5-th degree polynomial that I solved numerically..

Cheers, Werner

Good job Werner - that's what I came up with!

I used HP Prime fsolve() with two equations (normal slopes, normal intercepts) and two unknowns (xf, xg).

   

Using the Primes SKETCH feature was interesting at first to guess/eyeball the proper normal line.
Find all posts by this user
Quote this message in a reply
11-21-2015, 01:46 AM
Post: #11
RE: Brain Teaser - Minimum distance between two curves
(11-18-2015 11:47 PM)Jonathan Cameron Wrote:  When I got rid of that assumption, I get a gory polynomial ...

\[
4x^5+6x^3-x^2=\frac{1}{8}
\]

This looks rather harmless to me.

Cheers
Thomas
Find all posts by this user
Quote this message in a reply
11-21-2015, 05:37 PM
Post: #12
RE: Brain Teaser - Minimum distance between two curves
(11-21-2015 01:46 AM)Thomas Klemm Wrote:  
(11-18-2015 11:47 PM)Jonathan Cameron Wrote:  When I got rid of that assumption, I get a gory polynomial ...

\[
4x^5+6x^3-x^2=\frac{1}{8}
\]

This looks rather harmless to me.

Cheers
Thomas

You are right; not too bad. I had not simplified it yet...

-Jonathan
Visit this user's website Find all posts by this user
Quote this message in a reply
11-21-2015, 09:39 PM
Post: #13
RE: Brain Teaser - Minimum distance between two curves
May I suggest a slight variation?
One can compute the distance between two arbitrary points on the curves as a function of two variables: x1, x2. Let D(x1,x2) be that function. It is fairly easy to compute its gradient G(x1,x2) which has two components. Then finding the minimum distance is equivalent to find (x1,x2) such that G(x1,x2)=(0,0). Let's then introduce an auxiliary function G2 which is the square of the module of G. G2(x1,x2) is now a scalar. The root of this function can be found by using a Newton algorithm extended at two dimensions. The only difficulty is that you have now to compute the gradient of G2 which is a bit tedious by hand. Being lazy, I used a numerical approximation.
After some iterations I ended up with:
x1=0.331696159945
x2=0.56807264531
d(x1,x2)=0.427592353669
The accuracy of the solution in that case is mainly dependent of the accuracy of the approximation of the gradient, which in turn is limited by the accuracy of the floating point operations.

Regards
Find all posts by this user
Quote this message in a reply
01-02-2016, 06:14 PM
Post: #14
RE: Brain Teaser - Minimum distance between two curves
1. The coordinates at f(x) are (x,x^2+1); at g(y) are (y,sqrt(y)). Using a global minimization for the distance, the lowest distance possible is ~0.427592 where x=~0.331695 and y=~0.568071.
2. This x is the (real) root of the equation 4*x^5+6*x^3-x^2=1/8
3. More precisely y is ~0.5680712803530178751565860996, but I could not find a single proper closed form for this.

Done with Mathematica/WolframAlpha.
Find all posts by this user
Quote this message in a reply
01-12-2016, 09:40 AM (This post was last modified: 01-12-2016 12:34 PM by Pekis.)
Post: #15
RE: Brain Teaser - Minimum distance between two curves
Thanks for your refreshing brain teaser.

f(x)=x2+1 => f'(x)=2x
g(x)=sqrt(x) => g'(x)=1/(2sqrt(x))

The normal equation on f at xf: Slope: -1/f'(xf) Intercept: f(xf)+xf/f'(xf)
-> y=-x/(2xf))+xf2+3/2

The normal equation on g at xg: Slope: -1/g'(xg) Intercept: g(xg)+xg/g'(xg)
-> y=-2sqrt(xg)x+(2xg+1)sqrt(xg)

Same normal => -1/(2xf) must be equal to -2sqrt(xg) and xf2+3/2 must be equal (2xg+1)sqrt(xg)

Leads to
xf=1/(4sqrt(xg)) (or xg=1/(16xf2)
and then
4xf5+6xf3-xf2-1/8=0

Only one real root: approx. 0.331695 for xf => approx. 0.56807 for xg

=> distance (xf,f(xf)) (xg,g(xg)) is approx. 0.42759
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)