update distance matrix between n points

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!

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.