Fast algorithm for finding the size of each connected component in a graph of 2D points I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a &quot;threshold&quot; distance), find $s_1, s_2, \dots, s_k$, the sizes of all connected components in $G$.
The vertices of the graph are 2-dimensional points and there is an edge between $v_1$ and $v_2$ if the Euclidian distance between them is less than a given distance $t$ (the threshold above), otherwise there is no edge between $v_1$ and $v_2$.
Up until now, I've tried DFS methods and also attempted to use a QuadTree to group together &quot;close enough&quot; points.
For the attempt at QTs, I subdivide the plane into cells the diameter of which is sufficiently small to guarantee connectedness, then traverse the tree upwards to find all the neighboring cells and check if they make more connected points.
What I'm asking for is a more efficient algorithm (mainly on the time complexity front) (can be completely different or an improvement on the above, I'm open to anything). For context, the size of the samples I'm dealing with is ~100K.
PS: I do realize there are various other answers dealing with how to determine the connected components of a generic graph, but I believe that in this case (2D points and the need to &quot;only&quot; find their sizes) could benefit from more efficient methods. I could be wrong but there is no better way to find out.
You can do it in $O(n \log n)$ time by forming an Euclidean minimum spanning tree, and then dropping any edge with length greater than $t$.