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$
6
  • $\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, 2017 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, 2017 at 22:39
  • 1
    $\begingroup$ Do you need the exact answer, or are you OK with an approximation? $\endgroup$
    – D.W.
    Aug 13, 2017 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$ Aug 13, 2017 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, 2017 at 9:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.