Multiple Distance Functions

This may be obvious, but if you are only worried about finding the answer then your problem is equivalent to numerically finding the zeros of the function:

g(M) = -fP(M) + fA(M) + fB(M) + fC(M) + ...

You could solve this via newton's method or something like that, and it would probably end out being just as fast or even faster than evaluating a closed form algebraic solution.

I'm a little worried that the solution might blow up since g(infinity)=0, so you may instead want to do the following manipulations before applying the rootfinding:

0 = -fP(M) + fA(M) + fB(M) + fC(M)
= -1/||M-P|| + 1/||M-A|| + 1/||M-B|| + 1/||M-C||

Multiply through to eliminate the denominator:
0 = -||M-A||*||M-B||*||M-C| + ||M-P||*||M-B||*||M-C|| + ... + ||M-P||*||M-A||*||M-B||.

Then find the zeros of this new function I call it h:
h(M) = -||M-A||*||M-B||*||M-C| + ||M-P||*||M-B||*||M-C|| + ... + ||M-P||*||M-A||*||M-B||

via your favorite root finding algorithm.

I do follow you as far as:
g(M) = -f_P(M) + f_A(M) + f_B(M) + f_C(M) + ...

I'm assuming that:
h(M) = -||M-A||*||M-B||*||M-C| + ||M-P||*||M-B||*||M-C|| + ... + ||M-P||*||M-A||*||M-B||
has:
||M-A|| = (((M.x-A.x)^2)+((M.y-A.y)^2))^0.5
||M-B|| = (((M.x-B.x)^2)+((M.y-B.y)^2))^0.5
and so on?

Fortunately, there will never be a case where "g(infinity) = 0", but this equation actually looks simpler to me.

I'm afraid I've never had a formal Calculus class, so finding the zeroes of that big mess, in whatever form, with Newton's method is beyond me. Any help?

Thanks,
G

Ahh yes the notation ||x|| means "length of x", so ||M-A|| = (((M.x-A.x)^2)+((M.y-A.y)^2))^0.5 like you say. Sorry for not clarifying that earlier.

The basic idea of most numerical root finders like newton's method is that you start with a guess point, then apply a procedure to to get a little closer to the solution, then apply the procedure again to get closer still, and keep repeating this until the error is within a desired tolerance. The problem with the original formulation was that choosing M bigger and bigger (in length) would make the error g(M) smaller and smaller because of the inverse, so if you keep applying the iteration your point might start becoming infinitely big. That's what was meant by g(infinity)=0 being a problem.

The wikipedia article in Newton's method seems pretty good, maybe check that out:
http://en.wikipedia.org/wiki/Newtons_method

I'm not sure how hard it will be to understand, depending on how much math you know? I could try to help you through understanding it if want to give a try reading the article and posting questions.

First question:
if h(M) = -||M-A||*||M-B||*||M-C| + ||M-P||*||M-B||*||M-C|| + ... + ||M-P||*||M-A||*||M-B||
then h'M) = ?
Is the best way to find this with Newton's difference quotient, or is there something else?

Lets start in 1D first, then we can move to many dimensions later. So imagine that all the points A,B,C,M, etc are all in 1D, so M the unknown is just the x position of the point.

Then h'(x) is the slope of the tangent line to h at point x. The "derivative" is just another name for the slope of the tangent line. Here is a diagram of what is happening if you apply newtons method to your problem in 1D:


We can get into how to actually calculate the slope of the tangent line once this makes some sense. Please let me know if I need to clarify.

Thank you.

I do know the basic idea of the derivative, but not a good way to calculate it. The graphical representation of Newton's Method is interesting. Nice drawing :-)

G

Ahh ok I hope I'm not booring you wiht such simple things.

To calculate the derivative in 1D, there are a few basic things you need to know. It's a little more complicated in higher dimensions but not *that* much more complicated. Here are the basic rules for functions f(x) and g(x) that will let you figure out many things (here ' means derivative):
1) (f + g)' = f' + g' (derivative of sum)
2) (f*g)' = f'*g + f*g' (derivative of product)
3) f(g)' = f'(g)*g' (derivative of a function of a function)
4) (x^p)' = p*x^(p-1) (derivative for power of x)

If you want to see why these things are true, you will have to learn some calculus, no way around that. Its not that hard, but you have to do a bit of work. The basic idea is to approximate the tangent line by passing a line through 2 nearby points on a curve, and see what happens when the points get infinitely close. But anyways these rules are true even if you don't know why, so you could use them.

For example of 4), (x^2)' = 2x. Another one is x' = 1. Another one is sqrt(x)' = (x^(1/2))' = (1/2)*x^(-1/2). See the pattern?

For example of using 2), (x*x^2)' = 1*x^2 + x*2x = 3x^2. It would come out the same if you just did (x*x^2)' = (x^3)' and used rule 4) only.

For example of 3) and 4), what is (sqrt(x^2+1))'? If you look at it like f(g)' where f(x) = x^(1/2) and g(x) = x^2+1, then the answer is ((1/2)*(x^2+1)^(-1/2))*(2x). This one is important so give it some thought.

Another important point is that if you take the derivative of an absolute value, then all you do is consider each case separately. For example, |x-p| = x-p for x>p and -(x-p) for xp and -1 for x
Ok, so now do you think you could calculate the derivative of:
-|x-A|*|x-B| + |x-P|*|x-B| + |x-P|*|x-A|

??

Hint: break it up into many pieces depending on what values x is between.

I have been looking at Wikipedia for my calculus stuff, so I've inferred a lot. I think the thing with approaching secant lines was Newton's difference quotient? I think I might have also gotten stuck at wondering what the product rule looks like with three terms...

As to your question, I'll try:
-|x-A|*|x-B| + |x-P|*|x-B| + |x-P|*|x-A|
I'm going to put in P = 3, A = -2, and B = -1 based on your sketch.
-|x+2|*|x+1| + |x-3|*|x+1| + |x-3|*|x+2|
I separate into:
-|x+2|*|x+1|, |x-3|*|x+1|, and |x-3|*|x+2|

The first part, "-|x+2|*|x+1|", goes to:
-(x+2)*(x+1) = -x² - 3x - 2 if x > -1
(x+2)*(x+1) = x² + 3x + 2 if -2 < x < -1
-(x+2)*(x+1) = -x² - 3x - 2 if x < -2
Derivatives being:
-2x - 3 if x > -1
2x + 3 if -2 < x < -1
-2x - 3 if x < -2

The second part, "+|x-3|*|x+1|", goes to:
(x-3)*(x+1) = x² - 2x - 3 if x > 3
-(x-3)*(x+1) = -x² + 2x + 3 if -1 < x < 3
(x-3)*(x+1) = x² - 2x - 3 if x < -1
Derivatives being:
2x - 2 if x > 3
-2x + 2 if -1 < x < 3
2x - 2 if x < -1

The third part, "+|x-3|*|x+2|", goes to:
(x-3)*(x+2) = x² - x - 6 if x > 3
-(x-3)*(x+2) = -x² + x + 6 if -2 < x < 3
(x-3)*(x+2) = x² - x - 6 if x < -2
Derivatives being:
2x - 1 if x > 3
-2x + 1 if -2 < x < 3
2x - 1 if x < -2

Combining all this, the function is:
(-x²-3x-2)+(x²-2x-3)+(x²-x-6) if x > 3
(-x²-3x-2)+(-x²+2x+3)+(-x²+x+6) if -1 < x < 3
(x²+3x+2)+(x²-2x-3)+(-x²+x+6) if -2 < x < -1
(-x²-3x-2)+(x²-2x-3)+(x²-x-6) if x < -2
or:
x² - 6x - 11 if x > 3
-3x² + 7 if -1 < x < 3
x² + 2x + 5 if -2 < x < -1
x² - 6x - 11 if x < -2
And the derivatives are (I hope):
2x - 6 if x > 3
-6x if -1 < x < 3
2x + 2 if -2 < x < -1
2x - 6 if x < -2

-G

[Edited by - Geometrian on February 15, 2009 12:56:27 PM]

Yeah that looks great.

About the product rule: the product rule for 3, 4, 5, etc multiplications is just the repeated application of the product rule for 2 multiplications. eg, for functions f(x), g(x), w(x):
(f*g*w)' = ((f*g)*w)' = (f*g)'*w + (f*g)*w'
= (f'*g + f*g')*w + f*g*w'
= f'*g*w + f*g'*w + f*g*w'

You can see that in each term of the sum, there is the derivative of one function being multiplied by every other function.

Ok a few things worth mentioning - if you order the labeling of your points A
For example, the derivative of (x-1)*(x-2)*...*(x-n) is going to be
x*(x-2)*...*(x-n) + x*(x-1)*(x-3)*...*(x-n) + ... + x*(x-1)*...*(x-(n-1))

Perhaps give some thought to how you might find the derivative of
-|x-A|*|x-B|*...*|x-N| + |x-P|*|x-B|*|x-C|*...*|x-N| + |x-P|*|x-A|*|x-C|*...*|x-N| + ... + |x-P|*|x-A|*|x-B|*...*|x-M|

You dont need to actually compute it, but just consider what the pattern is and how you would find the derivative for each term if you wanted to write a program to do it.

Ok, before we go on to higher dimensions, do you think you now have the knowledge to write a program that solves the 1D version of your problem? Any other questions maybe I can try to help with at this point?

I think I'm ready.

Ok, try your hand at this article:
http://en.wikipedia.org/wiki/Newton%27s_method_in_optimization

(Newton's method in Optimization)

In 1-dimensionl Newton's method, we took information about the function h(m_n) and its derivative h'(m_n) at the n'th iteration point m_n, and then we used that to come up with a "better guess" m_(n+1) for the n+1'th iteration. It turns out that the process has a simple graphical explanation having to do with drawing tangent lines.

In higher dimensions, the function h(x,y,z,...) can "curve around" in many directions, so for Newton's method to work you have to include information about the function itself, the first derivative, AND the second derivative. There is probably a simple graphical explanation of it, but I don't know what it is (thats kind of an interesting question, maybe I'll give it some thought). Usually the justification for Newton's method comes from a very interesting but somewhat technical subject in calculus called taylor series, rather than the graphical explanation.

Also, there is the question of "what is meant by the first or second derivative in multidimensions?". This is where the concepts of the gradient and Hessian matrix come in. In there there are links to articles about the gradient (the slope and direction of the steepest possible tangent line on a multidimensional function), and the Hessian matrix (a sort of "multidimensional second derivative"), which you can have a look at.

[Edited by - Maze Master on February 17, 2009 3:33:18 AM]

I'm sorry, I made a big mistake in the last post. My bad. Newton's method in optimization finds the maxima or minima of a function, not it's zeros. The correct geometric interpretation is that it constructs the best possible parabola fit near point x_n, and then jumps to the minima of the parabola for point x_(n+1).

It's still salvagable, though. All you have to do is recast your problem as finding the minima of a function, not it's zeros. Thankfully, the problem is equivalent to finding a certain minima of the following function w(x):

w(x) = (1+h(x)^2)^(1/2)

If you wonder where this "w" function is coming from, it's basically like taking the absolute value, except the bottom of the sharp angle is smoothed out so everything is differentiable.

Here are some diagrams, this is where the (1+h(x)^2)^(1/2) is coming from:


And here is the effect of transforming h(x) to w(x) in 1D, and a picture showing Newton's method for finding minima and maxima in 1D (this generalizes to higher dimensions, the zero finding does not):


Once again I hope I didn't confuse you too much with the last post.

[Edited by - Maze Master on February 17, 2009 3:47:44 AM]

Hi,

My project has changed quite a lot. Many things have happened, and the problem has now changed, so unfortunately the problem can't be solved this way.

On the other hand, you've helped me learn some good calculus and helped get this far.

I've learned a lot, my sincere thanks!
Geometrian