Results 1 to 7 of 7

Math Help - Finding unknown path lengths

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    13

    Finding unknown path lengths

    I imagine this is a very basic question, but I am having a real problem finding the answer. I think the big issue is I don't know the proper vocabulary to express my question in mathematically, so my searches just aren't turning up the right kinds of results.

    Anyway, say I have an arbitrarily large number of points in space (I have upwards of 20,000 in my data set). I know the distances or path lengths between some of them, but not all of them. How do I go about using the known path lengths to calculate the unknowns?

    I know how to do this by hand with a small number of points. That's easy. But there must be some sort of method for determining this based on very very large data sets?

    So, to make my example more clear, say I have this matrix of values. Each value is the distance between the point indicated by the row and the point indicated by the column. Blank cells indicate that the distance for those points is unknown.


    A B C D
    A 0 5 10 7
    B 5 0 2
    C 10 0
    D 7 2 0

    So, in this simplified case, we have four points. A, B, C, and D. We know the distances between A and B, A and C, A and D, and B and D. We do not know the distances between B and C or between C and D.

    What sort of method would solve for those values?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2013
    From
    BC, Canada
    Posts
    95
    Thanks
    15

    Re: Finding unknown path lengths

    Quote Originally Posted by RASimmons View Post
    I imagine this is a very basic question, but I am having a real problem finding the answer. I think the big issue is I don't know the proper vocabulary to express my question in mathematically, so my searches just aren't turning up the right kinds of results.

    Anyway, say I have an arbitrarily large number of points in space (I have upwards of 20,000 in my data set). I know the distances or path lengths between some of them, but not all of them. How do I go about using the known path lengths to calculate the unknowns?

    I know how to do this by hand with a small number of points. That's easy. But there must be some sort of method for determining this based on very very large data sets?

    So, to make my example more clear, say I have this matrix of values. Each value is the distance between the point indicated by the row and the point indicated by the column. Blank cells indicate that the distance for those points is unknown.


    A B C D
    A 0 5 10 7
    B 5 0 2
    C 10 0
    D 7 2 0

    So, in this simplified case, we have four points. A, B, C, and D. We know the distances between A and B, A and C, A and D, and B and D. We do not know the distances between B and C or between C and D.

    What sort of method would solve for those values?
    To help, we need to know the properties of the "distance". Is it true that the distance between B and C is the sum of the distance from B to A and A to C? i.e. d(B,C) = d(B,A) + d(A,C)? (in this case, that would be 15)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    13

    Re: Finding unknown path lengths

    Quote Originally Posted by majamin View Post
    Is it true that the distance between B and C is the sum of the distance from B to A and A to C? i.e. d(B,C) = d(B,A) + d(A,C)? (in this case, that would be 15)
    No. The points are not arranged linearly. Even though we know the distances between points, we don't know their absolute positions, only the relative distances.

    We don't even necessarily know the dimensionality of these points - it could be in 2, 3, or more dimensions. I imagine the degree of dimensionality will change the calculations required, however.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2013
    From
    BC, Canada
    Posts
    95
    Thanks
    15

    Re: Finding unknown path lengths

    Quote Originally Posted by RASimmons View Post
    No. The points are not arranged linearly. Even though we know the distances between points, we don't know their absolute positions, only the relative distances.

    We don't even necessarily know the dimensionality of these points - it could be in 2, 3, or more dimensions. I imagine the degree of dimensionality will change the calculations required, however.
    Solving for the values depends on the properties of this "distance". Can you clarify on this? Furthermore, even if we knew the dimension, there wouldn't be enough information in the matrix (there would be many possible distances).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2011
    Posts
    13

    Re: Finding unknown path lengths

    Quote Originally Posted by majamin View Post
    Solving for the values depends on the properties of this "distance". Can you clarify on this?
    I just don't understand what you mean by "properties." Exactly what information do you need?

    Quote Originally Posted by majamin View Post
    Furthermore, even if we knew the dimension, there wouldn't be enough information in the matrix (there would be many possible distances).
    Wouldn't that only be true for increasing dimensionality? For example, if this is in a one-dimensional plane, there is only going to be one correct value for each distance. In a two-dimensional plane, there could be 2 possible correct values, etc. However, there aren't going to be an arbitrarily large number of possible correct distances because they are constrained by the distances we do know. And my real data set contained thousands upon thousands of values, which actually constrains things even further - say we have 2210 known distances from one point to other points and only one unknown, there are not going to be infinite possible values for that unknown.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2013
    From
    BC, Canada
    Posts
    95
    Thanks
    15

    Re: Finding unknown path lengths

    Quote Originally Posted by RASimmons View Post
    I just don't understand what you mean by "properties." Exactly what information do you need?
    There has to be some way to be able to calculate the distance, as by a formula or algorithm. Essentially, you need to know the properties of the "space" that you are working in.

    Quote Originally Posted by RASimmons View Post
    Wouldn't that only be true for increasing dimensionality? For example, if this is in a one-dimensional plane, there is only going to be one correct value for each distance. In a two-dimensional plane, there could be 2 possible correct values, etc. However, there aren't going to be an arbitrarily large number of possible correct distances because they are constrained by the distances we do know. And my real data set contained thousands upon thousands of values, which actually constrains things even further - say we have 2210 known distances from one point to other points and only one unknown, there are not going to be infinite possible values for that unknown.
    Given a large data set, it is possible to fix a certain distance, but you would still need know about the properties of the "distance". For instance, is it Cartesian? (i.e. d^2 = x^2 + y^2) or is it a "taxi cab metric" |d| = |x| + |y| (imagine a staircase going from one point to another)? How are you defining distance?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2011
    Posts
    13

    Re: Finding unknown path lengths

    Quote Originally Posted by majamin View Post
    There has to be some way to be able to calculate the distance, as by a formula or algorithm. Essentially, you need to know the properties of the "space" that you are working in.

    Given a large data set, it is possible to fix a certain distance, but you would still need know about the properties of the "distance". For instance, is it Cartesian? (i.e. d^2 = x^2 + y^2) or is it a "taxi cab metric" |d| = |x| + |y| (imagine a staircase going from one point to another)? How are you defining distance?
    I see. We are treating our data as Cartesian.

    In our situation we are actually working with a dissimilarity matrix. So the "distance" is actual just the difference between dissimilarity scores between the stimuli specified by the row and that specified by the column. In our case, the dissimilarity "scores" are determined by examining neuronal activity patterns. So, the "distance" represents the degree of difference between these firing patterns.

    That is our specific data set. However, I am interested in this technique for a variety of reasons not limited to analysis of this particular data set. So even if you think this is not an appropriate method for our data, I am still interested in figuring out how to do it, assuming Cartesian distance.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. finding lengths of curves
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 26th 2010, 06:41 AM
  2. Finding arc lengths
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 6th 2009, 07:28 AM
  3. finding lengths of this shape :/
    Posted in the Geometry Forum
    Replies: 1
    Last Post: June 3rd 2009, 12:56 AM
  4. Finding Lengths Geometry.
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: December 5th 2008, 11:08 AM
  5. Finding Missing Triangle Lengths...
    Posted in the Trigonometry Forum
    Replies: 36
    Last Post: April 1st 2008, 10:01 AM

Search Tags


/mathhelpforum @mathhelpforum