# 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 "threshold" 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 "close enough" 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 "only" find their sizes) could benefit from more efficient methods. I could be wrong but there is no better way to find out.

• And must the answer be exact, or are estimation algorithms okay too? – orlp Mar 23 at 21:02
• The answer must be exact. I'm not sure about how estimation algorithms would work but perhaps one can control the probability of error to a "reasonable" degree? For your first comment, I added an edit to clarify (but your guesses were exact). – FuzzyPixelz Mar 23 at 21:07
• Please don't just append "Edit: stuff". Instead, revise the question so it reads well for someone who encounters it for the first time. No need to mark what has changed. See cs.meta.stackexchange.com/q/657/755 – D.W. Mar 24 at 5:38

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$$.