3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ And must the answer be exact, or are estimation algorithms okay too? $\endgroup$
    – orlp
    Mar 23, 2021 at 21:02
  • $\begingroup$ 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). $\endgroup$
    – FuzzyPixelz
    Mar 23, 2021 at 21:07
  • 1
    $\begingroup$ 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 $\endgroup$
    – D.W. ♦
    Mar 24, 2021 at 5:38

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ As I will need to implement this in Python without the help of external modules, do you think a "DIY" code would be significantly slower than what Scipy offers for example? $\endgroup$
    – FuzzyPixelz
    Mar 24, 2021 at 9:29
  • $\begingroup$ @FuzzyPixelz That depends on the exact primitive that scipy offers and how relevant it is to your problem, but it's very well possible. $\endgroup$
    – orlp
    Mar 24, 2021 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.