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

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

$\endgroup$
  • 1
    $\begingroup$ Could you explain how the rules are for calculating the total distance? $\endgroup$ – Erik Kjellgren Aug 13 '17 at 18:59
  • $\begingroup$ @ErikKjellgren 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. $\endgroup$ – Mike Aug 13 '17 at 22:21
  • 1
    $\begingroup$ Can you please write down the mathematical formula for your distance calculation and update your question accordingly? You description is still unclear to me. $\endgroup$ – Bort Aug 14 '17 at 10:12
  • $\begingroup$ @Bort added description in the question $\endgroup$ – Mike Aug 14 '17 at 11:10
  • $\begingroup$ @H. Rittich What was wrong with the answer you provided? I still had time complexity of $O(n^2)$, but it looked like the number of operations would be smaller. $\endgroup$ – Mike Aug 16 '17 at 9:35
4
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.