# Total distance between points on a grid with time complexity lower than $O(n^2)$

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)$.

An example of a grid with $n=5$ would be the following set of points: $(1,0)$, $(0,1)$, $(2,0)$, $(2,1)$, $(2,2)$. As you can see their $x$ and $y$ coordinates can only have values from set $\{ 0, 1, 2\}$. (Thought usually n is very big $\approx 10^6$ )

In CS I would represent the grid as a matrix:

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

In order to calculate the TOTAL distance between points I follow the procedure:

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 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.

I fixed the calculations.

• Welcome to CS.SE! What do you mean by the total distance of those points? I know what the distance between two points means, but not what the total distance of a grid is. I also don't know what is happening in your calculations below. Can you give a self-contained specification of the problem? Also, what have you tried? It sounds like you already have an algorithm, so have you answered your own question? – D.W. Aug 12 '17 at 22:20
• I added a description in the EDIT section and fixed the calculations - it's simply calculating pairwaise distance and adding it up. The current algorithm bases on performing near $n^2$ calculations which is too much for large grids ($n \approx 10^6$) – Mike Aug 12 '17 at 22:39
• Do you need the exact answer, or are you OK with an approximation? – D.W. Aug 13 '17 at 1:24
• Can you explain what you mean by "which doesn't take into account the fact that they are positions in layers"? – Yuval Filmus Aug 13 '17 at 2:47
• @D.W. I need the exact answer, but depending of the quality of the approximation it might be useful as well. – Mike Aug 13 '17 at 9:03