Brain Teaser  Minimum distance between two curves

11182015, 04:35 PM
(This post was last modified: 11182015 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? 

11182015, 05:50 PM
(This post was last modified: 11182015 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.
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. 

11182015, 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. 

11182015, 06:24 PM
(This post was last modified: 11182015 06:27 PM by Vtile.)
Post: #4




RE: Brain Teaser  Minimum distance between two curves
(11182015 06:18 PM)Gerald H Wrote: Sorry, CR Haeger, my maths isn't up to it, but I'm interested in the answer. I'm not a great mathematician, but graphical solution with somekind of accuracy is easy with one tool that pathfinders use. 

11182015, 06:40 PM
Post: #5




RE: Brain Teaser  Minimum distance between two curves
(11182015 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. x = cube root (1/16) Hint: must be tangent point of both curves Jonathan 

11182015, 07:06 PM
(This post was last modified: 11182015 08:03 PM by CR Haeger.)
Post: #6




RE: Brain Teaser  Minimum distance between two curves
(11182015 06:40 PM)Jonathan Cameron Wrote:(11182015 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. 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. 

11182015, 07:23 PM
(This post was last modified: 11182015 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. 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. 

11182015, 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 5th degree polynomial that I solved numerically.. Cheers, Werner 

11182015, 11:47 PM
Post: #9




RE: Brain Teaser  Minimum distance between two curves
(11182015 07:06 PM)CR Haeger Wrote:(11182015 06:40 PM)Jonathan Cameron Wrote: x = cube root (1/16) 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... 

11192015, 12:30 AM
(This post was last modified: 11192015 04:51 PM by CR Haeger.)
Post: #10




RE: Brain Teaser  Minimum distance between two curves
(11182015 10:19 PM)Werner Wrote: xf = 0.331694745644, xg = 0.568071280353, distance = 0.427592353667 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. 

11212015, 01:46 AM
Post: #11




RE: Brain Teaser  Minimum distance between two curves  
11212015, 05:37 PM
Post: #12




RE: Brain Teaser  Minimum distance between two curves  
11212015, 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 

01022016, 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^3x^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. 

01122016, 09:40 AM
(This post was last modified: 01122016 12:34 PM by Pekis.)
Post: #15




RE: Brain Teaser  Minimum distance between two curves
Thanks for your refreshing brain teaser.
f(x)=x^{2}+1 => f'(x)=2x g(x)=sqrt(x) => g'(x)=1/(2sqrt(x)) The normal equation on f at x_{f}: Slope: 1/f'(x_{f}) Intercept: f(x_{f})+x_{f}/f'(x_{f}) > y=x/(2x_{f}))+x_{f}^{2}+3/2 The normal equation on g at x_{g}: Slope: 1/g'(x_{g}) Intercept: g(x_{g})+x_{g}/g'(x_{g}) > y=2sqrt(x_{g})x+(2x_{g}+1)sqrt(x_{g}) Same normal => 1/(2x_{f}) must be equal to 2sqrt(x_{g}) and x_{f}^{2}+3/2 must be equal (2x_{g}+1)sqrt(x_{g}) Leads to x_{f}=1/(4sqrt(x_{g})) (or x_{g}=1/(16x_{f}^{2}) and then 4x_{f}^{5}+6x_{f}^{3}x_{f}^{2}1/8=0 Only one real root: approx. 0.331695 for x_{f} => approx. 0.56807 for x_{g} => distance (x_{f},f(x_{f})) (x_{g},g(x_{g})) is approx. 0.42759 

« Next Oldest  Next Newest »

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