Let's suppose that I have n points, and a square numpy matrix where i,j'th entry is filled with the distance between the point i and point j. How can I derive an adjacency matrix in a way that, there is an "edge" between point a and point b if for every other point c, max(dist(c,a), dist(c,b)) > dist(a,b), in other words there is not any other point c such as c is closer to a and b than, a and b are to each other. I could write this in numpy with some for loops, but I wonder if there is any easier/faster way to do so.

EDIT: I think it is kinda similar to finding the 'closure' of points. e.g, if we have 4 vertices of a rectangle we only draw the sides (4 edges)

CodePudding user response：

This is really hard to do without a concrete example, so I may be getting this slightly wrong.

So you have an nxn matrix (presumably symmetric with a diagonal of 0) representing the distances. Let's call this matrix A.

Then A[:,None,:] is an nx1xn matrix such that if you broadcast it to nxnxn, then A[i, j, k] is the distance from the i'th point to the k'th point. Likewise, A[None, :, :], when broadcast to nxnxn, gives a matrix such that A[i, j, k] gives the distance from the j'th point to the kth point.

So B = np.maximum(A[:,None,:],A[None,:,:]) is an array such at b[i, j, k] is the maximum of the distance from i to k or from j to k. Take the minimum of B along the last dimension, and you've got the value for the best possible k. Edges are those values for which np.min(B, axis=2) <= A.

Again, try this out on your own computer. I may have slight details wrong.