1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Aug 12 '17 at 22:20
  • $\begingroup$ 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$) $\endgroup$ – Mike Aug 12 '17 at 22:39
  • 1
    $\begingroup$ Do you need the exact answer, or are you OK with an approximation? $\endgroup$ – D.W. Aug 13 '17 at 1:24
  • $\begingroup$ Can you explain what you mean by "which doesn't take into account the fact that they are positions in layers"? $\endgroup$ – Yuval Filmus Aug 13 '17 at 2:47
  • $\begingroup$ @D.W. I need the exact answer, but depending of the quality of the approximation it might be useful as well. $\endgroup$ – Mike Aug 13 '17 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.