computing distances

[drago]

Hi,
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

drago

[mathwonk]

are you sure your indices are correct on the last terms of your expressions, Sj?

[drago]

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!

drago

[drago]

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:
(qn-1)
(y0) //y after the n-1st shift

drago