Brain Teaser - Minimum distance between two curves - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: Not HP Calculators (/forum-7.html) +--- Forum: Not remotely HP Calculators (/forum-9.html) +--- Thread: Brain Teaser - Minimum distance between two curves (/thread-5155.html) |
Brain Teaser - Minimum distance between two curves - CR Haeger - 11-18-2015 04:35 PM 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? [attachment=2811] 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? RE: Brain Teaser - Minimum distance between two curves - Vtile - 11-18-2015 05:50 PM ."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. RE: Brain Teaser - Minimum distance between two curves - Gerald H - 11-18-2015 06:18 PM 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. RE: Brain Teaser - Minimum distance between two curves - Vtile - 11-18-2015 06:24 PM (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. I'm not a great mathematician, but graphical solution with somekind of accuracy is easy with one tool that pathfinders use. RE: Brain Teaser - Minimum distance between two curves - Jonathan Cameron - 11-18-2015 06:40 PM (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. x = cube root (1/16) Hint: must be tangent point of both curves -Jonathan RE: Brain Teaser - Minimum distance between two curves - CR Haeger - 11-18-2015 07:06 PM (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. 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. RE: Brain Teaser - Minimum distance between two curves - Vtile - 11-18-2015 07:23 PM 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. RE: Brain Teaser - Minimum distance between two curves - Werner - 11-18-2015 10:19 PM 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 RE: Brain Teaser - Minimum distance between two curves - Jonathan Cameron - 11-18-2015 11:47 PM (11-18-2015 07:06 PM)CR Haeger Wrote:(11-18-2015 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... RE: Brain Teaser - Minimum distance between two curves - CR Haeger - 11-19-2015 12:30 AM (11-18-2015 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). [attachment=2813] Using the Primes SKETCH feature was interesting at first to guess/eyeball the proper normal line. RE: Brain Teaser - Minimum distance between two curves - Thomas Klemm - 11-21-2015 01:46 AM (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 RE: Brain Teaser - Minimum distance between two curves - Jonathan Cameron - 11-21-2015 05:37 PM (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 ... You are right; not too bad. I had not simplified it yet... -Jonathan RE: Brain Teaser - Minimum distance between two curves - Bunuel66 - 11-21-2015 09:39 PM 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 RE: Brain Teaser - Minimum distance between two curves - quinyu - 01-02-2016 06:14 PM 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. RE: Brain Teaser - Minimum distance between two curves - Pekis - 01-12-2016 09:40 AM 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 |