I was looking to find out if anyone knows of an optimal method to find the squared distance of a path defined by a series of 3D points?
Given an arbitrary array of vectors, find the squared sum of the distance between each points and its previous point I mean.
To my knowledge in order to do this you have to sum up all the distances and then square the result. But was wondering if there was a tricky way to do this only using the squared distance between each of the points.
You can't get the exact value of the squared sum of all the lengths just from the squared lengths, but you CAN get some nice bounds, if that helps.
For any a1, a2, ..., an >= 0, the lower bound
(a1 + a2 + ... + an)^2 >= a1^2 + a2^2 + ... + an^2
holds.
Furthermore, if you can guarantee that a1^2, a2^2, ..., an^2 are all greater than or equal to 1, then additionally the upper bound
(a1 + a2 + ... + an)^2 <= a1^2 + a2^2 + ... + an^2 + 2*a1^2*a2^2 + 2*a1^2*a3^2 + ... + 2*a1^2*an^2 + 2*a2^2*a3^2 + ...
also holds.
In case you have trouble following all those coefficients and exponents and stuff, the latter term (after the "+ an^2 + ") is
for i in [1,n]
for j in [i+1,n]
sum += 2 * ai^2 * aj^2
The good part about that upper bound condition is that you can easily make sure it holds by scaling the grid accordingly. It's an O(n^2) operation, but so is calculating the upper bound.
Hope that helps a bit!
