Total distance between points on a grid

Question

I have $n$ points that form a grid with empty space and I need to find an algorithm that would calculate the total distance of those points with time complexity lower than $O(n^2)$.

a grid with $n=5$ could be represented as a matrix:

$$ \begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{matrix} $$

the distance for point $(1,3)$ is: $1+\sqrt{5}+2+\sqrt{5}=3+2\sqrt{5}$

the distance for point $(2,1)$ is: $2+\sqrt{2}+\sqrt{5}$

the distance for point $(2,3)$ is: $\sqrt{2}+1$

the distance for point $(3,2)$ is: $1$

the distance for point $(3,3)$ is: $0$

So the total distance is: $7+2\sqrt{2}+3\sqrt{5}$

This approach simply calculates separately the distance and then adds it up which doesn't take into account the fact that they are positions in layers.

This doesn't look like a super unique issue - is there any existing algorithm for this or does anyone have an idea how to speed this up?

EDIT: By Total Distance I mean a situation like this: I pick a point and then calculate the euclidean distance between the picked point and the rest $n-1$ points. Then I choose the next point and I calculate it's distance betwenn it and the rest $n-2$ points, and so on. I then sum up all the distances to get the total.

Explanation for distance calculation: The distance for point $(1,3)$ is the sum of euclidean distances between point $(1,3)$ and $(2,1)$, $(2,3)$, $(3, 2)$, $(3,3)$. The distance for point $(2,1)$ is the sum of euclidean distances between point $(2,1)$ and $(2,3)$, $(3, 2)$, $(3,3)$. and so on...

Answer 1

If I understand the questions correctly, you have the following situation. Be $S=\{x_1,\ldots,x_n\}$ the set of points. You need to calculate the total distance $d_t$of $S$, defined as$$d_t=\sum_{j=1}^{n-1}\sum_{i_j=j+1}^n |x_{i_j}-x_j|$$.

This definition is equivalent to the sum of the upper or lower triangle matrix of the distance matrix of the set S.

$$D=\left(\begin{array}{cccc} 0&x_{12}&x_{13}&\ldots &x_{1n}\\ x_{21}&0&x_{23}&\ldots &x_{2n}\\ \vdots && \ddots && \vdots \\ x_{n1}&x_{n2} &\ldots &&0 \\ \end{array}\right)$$ Here $x_{ij}=|x_i-x_j|$.To calculate the distance matrix alone you need $n(n-1)/2=O(n^2)$ operations. So no, I am not aware of an algorithm which is better than $O(n^2)$.

If an approximation to $d_t$ is in order, than you can use nearest neighbor search algorithms which do better than $O(n^2)$ and sum only those distance pairs which dominate the sum.