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
 CR Haeger Member Posts: 275 Joined: Dec 2013
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?
11-18-2015, 05:50 PM (This post was last modified: 11-18-2015 06:25 PM by Vtile.)
Post: #2
 Vtile Senior Member Posts: 385 Joined: Oct 2015
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.

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.
11-18-2015, 06:18 PM
Post: #3
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
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.
11-18-2015, 06:24 PM (This post was last modified: 11-18-2015 06:27 PM by Vtile.)
Post: #4
 Vtile Senior Member Posts: 385 Joined: Oct 2015
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.
11-18-2015, 06:40 PM
Post: #5
 Jonathan Cameron Member Posts: 205 Joined: Dec 2013
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
11-18-2015, 07:06 PM (This post was last modified: 11-18-2015 08:03 PM by CR Haeger.)
Post: #6
 CR Haeger Member Posts: 275 Joined: Dec 2013
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.
11-18-2015, 07:23 PM (This post was last modified: 11-18-2015 10:11 PM by Vtile.)
Post: #7
 Vtile Senior Member Posts: 385 Joined: Oct 2015
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.

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.
11-18-2015, 10:19 PM
Post: #8
 Werner Senior Member Posts: 557 Joined: Dec 2013
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
11-18-2015, 11:47 PM
Post: #9
 Jonathan Cameron Member Posts: 205 Joined: Dec 2013
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...
11-19-2015, 12:30 AM (This post was last modified: 11-19-2015 04:51 PM by CR Haeger.)
Post: #10
 CR Haeger Member Posts: 275 Joined: Dec 2013
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.
11-21-2015, 01:46 AM
Post: #11
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
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
11-21-2015, 05:37 PM
Post: #12
 Jonathan Cameron Member Posts: 205 Joined: Dec 2013
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
11-21-2015, 09:39 PM
Post: #13
 Bunuel66 On Vacation Posts: 29 Joined: Jan 2014
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
01-02-2016, 06:14 PM
Post: #14
 quinyu Junior Member Posts: 44 Joined: Dec 2015
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.
01-12-2016, 09:40 AM (This post was last modified: 01-12-2016 12:34 PM by Pekis.)
Post: #15
 Pekis Member Posts: 115 Joined: Aug 2014
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)

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
 « Next Oldest | Next Newest »

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