Algorithm for distance from point to function 
Author Message
 Algorithm for distance from point to function

A bit off-topic, but where better to ask?

Does there exist any reasonably general algorithm for computer
the distance between the point (x,y) and a function y = f(x)?

Mike

Mike Prager
North Carolina, USA



Wed, 31 Dec 2008 06:34:10 GMT  
 Algorithm for distance from point to function

Quote:

>Does there exist any reasonably general algorithm for computer
>the distance between the point (x,y) and a function y = f(x)?

Minimize sqrt((xi-x)**2 + (f(xi)-y)**2).


Wed, 31 Dec 2008 20:21:38 GMT  
 Algorithm for distance from point to function

Quote:


>>Does there exist any reasonably general algorithm for computer
>>the distance between the point (x,y) and a function y = f(x)?
> Minimize sqrt((xi-x)**2 + (f(xi)-y)**2).

There may be local minima, so you might want a routine that
is good at finding a global minimum.  It is only one dimension,
so it shouldn't be too hard.

I usually look in Numerical Recipes.

-- glen



Thu, 01 Jan 2009 01:07:39 GMT  
 Algorithm for distance from point to function

Quote:



> >>Does there exist any reasonably general algorithm for computer
> >>the distance between the point (x,y) and a function y = f(x)?

> > Minimize sqrt((xi-x)**2 + (f(xi)-y)**2).

> There may be local minima, so you might want a routine that
> is good at finding a global minimum.  It is only one dimension,
> so it shouldn't be too hard.

> I usually look in Numerical Recipes.

> -- glen

There are at least two ways to look at this. Suppose that the point is
(a,b).

1. Simplify the problem by minimizing the distance squared instead of
the distance. See the recent discussion in this newsgrop of Cernlib's
MINFC.

2. Take the derivative of the distance squared and set it equal to
zero. Equivalently, note that the distance will be minimal where the
line from the point to the curve is perpendicular to the tangent line
to the curve or when their slopes are negative reciprocals.

(y-b)/(x-a) f'(x) = -1 where y=f(x), solve for (x,y).

-- elliot



Thu, 01 Jan 2009 03:26:34 GMT  
 Algorithm for distance from point to function
The minimum distance is the length of the shortest line from the point
x1y1 to a tangent to the line y=f(x). The equation of the tangent is a
line whose slope is the first derivative at x2y2. The point x2,y2
satisfying the function and at the shortest distance is the
intersection of  a line through x1y1 which is perpendicular to the
tangent at x2,y2 and therefore has a slope of the inverse of the tanget
(or the reciprocal of the first derivative at that point).
Then the distance is just the normal Gausian square rooot of the sum of
the squares of the differences between each coordinate of the pair
x1,y1;  x2,y2
Searching by closer approximations is the best technique.


Thu, 01 Jan 2009 08:13:58 GMT  
 Algorithm for distance from point to function

Quote:

> The minimum distance is the length of the shortest line from the point
> x1y1 to a tangent to the line y=f(x). The equation of the tangent is a
> line whose slope is the first derivative at x2y2. The point x2,y2
> satisfying the function and at the shortest distance is the
> intersection of  a line through x1y1 which is perpendicular to the
> tangent at x2,y2 and therefore has a slope of the inverse of the tanget
> (or the reciprocal of the first derivative at that point).
> Then the distance is just the normal Gausian square rooot of the sum of
> the squares of the differences between each coordinate of the pair
> x1,y1;  x2,y2
> Searching by closer approximations is the best technique.

Thanks to all who posted hints.  We had indeed been planning
to use an optimization in finding the shortest distance. The
function to which we are finding distance is monotonic, and I
think that will simplify things a bit.  It may even be
possible that we can use the derivative of the distance --
we'll have to examine that closely.

I was hoping that there might be a magic bullet we had
overlooked, but (not surprisingly) it appears not.

Because the distances are needed for an outer optimization
(fitting by least squared distances), this is becoming
computationally intense.  Luckily, the data sets are small.

...Mike

Mike Prager
North Carolina, USA



Thu, 01 Jan 2009 12:34:29 GMT  
 Algorithm for distance from point to function

Quote:


>> The minimum distance is the length of the shortest line from the point
>> x1y1 to a tangent to the line y=f(x).

>Thanks to all who posted hints.  We had indeed been planning
>to use an optimization in finding the shortest distance. The
>function to which we are finding distance is monotonic, and I
>think that will simplify things a bit.  It may even be
>possible that we can use the derivative of the distance --
>we'll have to examine that closely.

If you only use derivatives you'll miss any maxima/minima that are
either at end-points of the curve or at points where f(x) is not
differentiable, which can of course happen even if f is monotonic.

-- John Harper, School of Mathematics, Statistics and Computer Science,
Victoria University, PO Box 600, Wellington 6140, New Zealand



Fri, 02 Jan 2009 06:10:12 GMT  
 Algorithm for distance from point to function

Quote:




>>> The minimum distance is the length of the shortest line from the point
>>> x1y1 to a tangent to the line y=f(x).

>>Thanks to all who posted hints.  We had indeed been planning
>>to use an optimization in finding the shortest distance. The
>>function to which we are finding distance is monotonic, and I
>>think that will simplify things a bit.  It may even be
>>possible that we can use the derivative of the distance --
>>we'll have to examine that closely.

>If you only use derivatives you'll miss any maxima/minima that are
>either at end-points of the curve or at points where f(x) is not
>differentiable, which can of course happen even if f is monotonic.

>-- John Harper, School of Mathematics, Statistics and Computer Science,
>Victoria University, PO Box 600, Wellington 6140, New Zealand


John, thanks for reminding me of this!

Mike

--
Mike Prager, NOAA, Beaufort, NC
Address spam-trapped; remove color to reply.
* Opinions expressed are personal and not represented otherwise.
* Any use of tradenames does not constitute a NOAA endor{*filter*}t.



Fri, 02 Jan 2009 21:52:20 GMT  
 Algorithm for distance from point to function

Quote:

> Does there exist any reasonably general algorithm for computer
> the distance between the point (x,y) and a function y = f(x)?

This is like asking if sea water is salty!? :)  AE, and its supply is
varied and plentiful.
You might consider the orthogonal least squares (haven't seen it
mentioned) which you can find on netlib. See http://netlib.org/odrpack

--
sdx
http://www.sdynamix.com



Mon, 05 Jan 2009 03:36:16 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. Genetic Algorithms: Hamming Distances

2. IndexedFaceSet - Algorithm for connecting points

3. Conversion algorithm between IEEE floating point and old Microsoft Binary Format

4. Needed: Algorithm for best fit vector of list of 3-d points

5. Change graph with points located at different distance, to equidistant points graph.

6. simplex algorithm - R. Agnew function

7. Algorithm for datebase function

8. sublist? function using Knuth-Morris-Pratt Algorithm

9. search algorithm for a math mod function (5 mod[2]=1)

10. Thanks to everybody for Gamma function algorithm

11. Gamma function algorithm

12. C, Pascal, or FORTRAN algorithms needed for Bessel function computation

 

 
Powered by phpBB® Forum Software