Given a set of vertices with 3D spatial coordinates of size N and a maximum connection distance d, is there an efficient algorithm to find all the undirected edges connecting the vertices with distance less than d; loops are not considered. A naive approach would simply loop on all possible pairs, requiring N(N-1)/2 distance calculations. Is there an existing algorithm for finding all possible edges with scaling complexity less than O(N^2)?

CodePudding user response：

Given a set of vertices with 3D spatial coordinates of size N and a maximum connection distance d, is there an efficient algorithm to find all the undirected edges connecting the vertices with distance less than d

Yes. Insert the vertex locations into a quadtree, then for each vertex search for vertices closer than d.

You can find C code to do this at

For more details, check out the German tv mini-series 'Billion Dollar Code' available on Netflix.