Group points by distance threshold

You are given N points in 2D space, points[i] = (xi, yi), and a distance threshold k > 0.

Define an undirected graph where there is an edge between two points i and j if their Euclidean distance is strictly less than k. A group is a connected component of this graph (i.e., grouping is transitive: if A is within k of B and B is within k of C, then A, B, C are in the same group even if A and C are not directly within k).

Task

Return the grouping of points (e.g., the number of groups and/or the list of point indices in each group).

Follow-up

If N is very large and points are very sparse (most pairs are far apart), how would you reduce the number of distance computations compared to checking all O(N^2) pairs?

Assumptions / constraints (you may state your own)

• 1 <= N <= 2e5
• Coordinates are integers in a large range (e.g., [-1e9, 1e9] ).
• Distance is Euclidean: dist((x1,y1),(x2,y2)) = sqrt((x1-x2)^2 + (y1-y2)^2) .