# Find squared length of path without using square root?

This topic is 631 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
You mean the length of the path squared? Unfortunately you can't avoid the square roots.

##### Share on other sites

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!

1. 1
2. 2
3. 3
Rutin
21
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 10
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013149
×