Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computing distances

  1. Sep 16, 2004 #1
    I would appreciate if you could point me some resources that you have seen and think could be related to the following problem:

    Given are the values of two polynomials Y(x) and Q(x) in n consecutive points (x0, x1,…, xn-1): (y0, y1,…,yn-1) and (q0, q1,…,qn-1) respectively.
    We would like to evaluate the following sums:

    S0 = (y0 – q0)^2 + (y1 – q1)^2 + …. + (yn-1 – qn-1)^2
    S1 = (y0 – q1)^2 + (y1 – q2)^2 + …. + (yn-2 – qn-1)^2
    S2 = (y0 – q2)^2 + (y1 – q3)^2 + …. + (yn-3 – qn-1)^2
    Sn-1 = (y0 – qn-1)^2

    Now, the question is, can I represent Sk as function of Sk-1? The point is, that I can evaluate Sk from the above representation, but this would have linear time complexity O(n), and there should be some way for this to be done in constant time, once we know S0 through Sk-1.

    Thank you

  2. jcsd
  3. Sep 18, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    are you sure your indices are correct on the last terms of your expressions, Sj?
  4. Sep 20, 2004 #3
    Yes, they are. That is as if we shift right the y segment one point at a time and compute the sum of the distances between the new segments leaving out the leftmost point of q and rigthmost point of y:

    for S0 : (q0, q1, ......., qn-1)
    (y0, y1, ......., yn-1)

    for S1: (q0, q1,........, qn-1)
    (y0, y1,..., yn-2, yn-1) //y shifted right
    for Sn-1: (q0, q1,........, qn-1)
    (y0, ........., yn-1)

    Well, the more I think about this, the more it seems to me that computing all of the sums cannot be done in less than O(n^2) time.

    Thank you anyway!

  5. Sep 20, 2004 #4
    Sorry, the example should be like that:

    for S1:
    (q1, ...., qn-1)
    (y0,....., yn-2) //y shifted rigth and compared with the remaining of q

    for Sn-1:
    (y0) //y after the n-1st shift

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook