1
$\begingroup$

I am looking for an efficient algorithm to update a $N*N$ matrix, in which the coefficients represents the distance between $N$ number of points, every time that the coordinates of a point change in a 2D Cartesian plane.

Here an example: There are 3 points in a Cartesian plane:

$a=(1,3)$ $b=(3,3)$ $c=(4,1)$

to calculate the distance between $a$ and $b$ I would simply apply:

$d_{ab} = \sqrt{(x_b-x_a)^2 + (y_b-y_a)^2}$

the distance matrix would be a $3*3$ diagonal matrix where the coefficients represent the distances between each point:

$\begin{bmatrix}0 & d_{ab} & d_{ac} \\ d_{ba} & 0 & d_{bc} \\ d_{ca} & d_{cb} & 0 \end{bmatrix}$

My algorithm is pretty straight forward: I nest 2 for loops to calculate the distance between each point that are inside the points array every time a coordinate change. Here an example in python, but I am not interested in a language specific solution:

import math
def distance(a,b):
    x = pow(b[0]-a[0], 2)
    y = pow(b[1]-a[1], 2)
    return math.sqrt(x+y)

points = [[1,3],[3,3],[4,1]]; # cartesian points
distanceMatr = [];
matrixLen = len(points);
for i in range(matrixLen):
    point = points[i]
    row = []
    for j in range(matrixLen):
        d = distance(point, points[j])
        row.append(d)

    distanceMatr.append(row)

print(distanceMatr)

If now $a$ moves to $(2,3)$ points becomes [[2,3],[3,3],[4,1]] and I apply the same algorithm again.

The main problems that I would like to optimise of this algorithm are:

  • if the coordinates of $a$ change the distance between $b$ and $c$ doesn't
  • the distance $d_{ab}$ is equal to $d_{ba}$
  • the distance between $a$ and itself is always $0$

Do you have any advice? thank you very much!

$\endgroup$

1 Answer 1

1
$\begingroup$

If the coordinates of $a$ change, you just need to update one row and one column corresponding to $a$, not the whole matrix. This is done in linear time rather than quadratic time in your algorithm.

$\endgroup$

Your Answer

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

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