Notices
Results 1 to 9 of 9

Thread: shortest path

  1. #1 shortest path 
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    We all know that the shortest path between any two points is a straight line, and I'm certainly not disputing this fact, but what is the actual proof for it?


    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    I suppose you mean in Euclidean space. I'll prove for n-dimensional space by induction.

    For n = 1, this is trivially true, as all paths are straight lines.

    Suppose it's true for some n ≥ 1. Then consider two points in n+1-dimensional space and a path between the two points. Take any n-dimensional hyperplane containing the two points. We can orthogonally project the path down to a path in this hyperplane. This new, projected path is at most as long as the original path--it moves in all of the same directions as the original path save for the direction orthogonal to the hyperplane. In fact, you can make this rigorous by considering the calculus definition of length--the length element for the new path would be bounded above by the length element for the old one because it's the same thing except movement in one direction has been changed to 0. In fact, this even shows that, unless the original path lies in the hyperplane, it is necessarily longer than the projected path, as the movement in this one direction must be nonzero at some point and hence on some interval. So, if our path is the shortest, it must lie in this n-dimensional hyperplane. But then the result for n dimensions says, for this new path to be shortest, it has to be a straight line.

    Actually, I don't even need induction. My above proof shows that a shortest path between two points in n-space must lie in every (n-1)-dimensional hyperplane containing the two points, and you can show that the intersection of all such hyperplanes is the line between the two points.

    When we're dealing with non-Euclidean space, we typically define lines by the property that they are the distance-minimizing paths through the space.


    Reply With Quote  
     

  4. #3  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,517
    You can also do this by minimizing the corresponding functional equation. Do you know anything about the calculus of variations?
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  5. #4  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    That is something I do not know. Care to enlighten?
    Reply With Quote  
     

  6. #5  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,517
    Hey serpicojr

    First we have to agree that a path is any C<sup>2</sup> function from R into the space in question. The maths is easiest to show for the 2d case so suppose (a<sub>1</sub>, b<sub>1</sub>) and (a<sub>2</sub>, b<sub>2</sub>) are two points in R<sup>2</sup> and that y=f(x) is a curve that joins those two points i.e. f(a<sub>i</sub>) = b<sub>i</sub>.

    Now the length of that curve is given by the following integral ∫ L(x, y, y') = ∫ (1 + f'(x))<sup>0.5</sup> dx and we wish to minimize this integral over all C<sup>2</sup> functions such that f(a<sub>i</sub>) = b<sub>i</sub>. The Euler-Lagrange equations come to our rescue (I can derive them if you want, else take these on faith if you haven't seen them) and we find that f is a critical point of that integral if d/dt L<sub>y'</sub> = L<sub>y</sub> where the subscripts here denote partial derivatives.

    This gives us the equation 0.5 d/dt (1+f'(x))<sup>-0.5</sup> = -0.25 (1 + f'(x))<sup>-1.5</sup> f''(x) = 0 which implies that f''(x) = 0 i.e. f is the straight line f(x) - b<sub>1</sub> = (b<sub>2</sub> - b<sub>1</sub>)/(a<sub>2</sub> - a<sub>1</sub>) (x - a<sub>1</sub>)

    I'm not sure about the C<sup>1</sup> case, will have to think about it.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  7. #6  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    I'm more than happy to assume C<sup>2</sup>, although feel free to share if you do work out the C<sup>1</sup> case. I filled in the gaps with Wikipedia, which gives a pretty good proof of the Euler-Lagrange equation for the 2-dimensional case.

    Oh, and I want to say that this proof is really slick!
    Reply With Quote  
     

  8. #7  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I think I kind of got that, serpicojr. Thanks. As for river_rat's proof...I think I'll be saving that for a later time.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  9. #8  
    Forum Sophomore numb3rs's Avatar
    Join Date
    Mar 2008
    Posts
    166
    im in 8th grade and u all are confuzling but ill try to answer
    i looked at this i took a pencil and put it in a strait line and then in a vertical line and it covers less of a distance going side ways then it does strait...
    Reply With Quote  
     

  10. #9  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    The important thing about Chemboy's question is that he's asking about paths between two specific points--i.e., he's asking about all possible ways to walk from point A to point B. There's only one line going through A and B, so we don't have to worry about any other lines when answering Chemboy's problem!

    The things we do have to worry about are curved paths--how do we know that it's not shorter to take some sort of curvy route from A to B? Indeed, if we start looking at more complicated forms of this question--for example, finding the shortest path from New York to San Francisco--we have to start taking things into account like the varying landforms of (you may cover more distance going over a mountain than going around it) the United States and the curvature of the earth.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •