Sum of distances without multiple square roots

Question

Here's my problem - I have multiple ordered points on a plane x₁, x₂, ... x_n, each with its own (x,y) position. I need to find the total distance between all adjacent points, i.e. dist(x₁, x₂) + dist(x₂, x₃) + ... + dist(x_n-1, x_n).

The problem - The square root function is considered resource heavy (it's supposed to be a computer algorithm) so I cannot take a square root for each distance (n may be very large). I need to find a way of calculating this without taking more than one square root for the entire calculation, or at the worst case a fixed number of square roots (i.e. the number of square roots is completely independent of n).

Each distance may be between 0 and 10000 and is not necessarily an integer (4 digit precision should be sufficient), which means that lookup tables will also be large and performing a lookup for each distance is probably also too resource heavy.

If this is too difficult or impossible - I actually only need to know if the sum of the distances exceeds a certain, fixed, known value. I don't really need to know the exact sum of distances, just need to know whether it's bigger than the threshold or not.

Thank you!

Answer 1

the Manhattan metric should provide an upper bound.

the Manhattan metric:

let $z_1=\langle x_1,y_1\rangle,\;z_2=\langle x_2,y_2\rangle$

$d(z_1,z_2)=|x_1-x_2|+|y_1-y_2|$

proof:

$(x_1-x_2)^2+(y_1-y_2)^2\leq (x_1-x_2)^2+\\2|x_1-x_2||y_1-y_2|+(y_1-y_2)^2=\\(|x_1-x_2|+|y_1-y_2|)^2$

Answer 2

Considering$$S=\sum_{k=1}^n d_k$$

using the AM-QM inequality, $\sqrt{n S}$ is an upper bound of $\sum_{k=1}^n\sqrt{d_k}$.

Using Mathematica with random integer between $0$ and $10,000$ (seed equal $1234$) and $n=10,000$

$$S=\sum_{k=1}^n d_k=49300823$$ $$\sum_{k=1}^n\sqrt{d_k}=660737.$$ $$\sqrt{n S}=702145.$$