Point Clustering algorithm

Question

I need help to solve a geometry problem . Consider a set of points. We note the number of points N.

We note d the euclidienne distance and dmax a value.

Two points p1 and p2 are connected if and only if the distance d(p1,p2)

The problem is to create an algorithm that returns a list of the size of connected components.

For example in the figure below the algorithm should return

[3, 2, 4, 1]

I drawed the connections in red but initially we only have the points (here in black). If needed the program should calculate all the connections. figure below

I have two algorithm one iterative and the other recursive. I used a DBScan. But it is not fast enough. Yhe complexity is O(N^2)

I need it to be faster with if possible an O(N) or O(N*log(N)).

I read about DFS but i am not really sure...

Thanks for help

user_2144669 · Answer

Use SciPy (or another library) to find the Delaunay triangulation of the input points (which contains the minimum spanning tree, which includes enough edges to make the rest of this answer work). Delete the edges of the triangulation that have length ≥ dmax. Find the connected components of the remaining edges.

This is O(n log n), with the inner loop in Qhull (a compiled extension).

(k-d tree or other locality structures offer another path to a solution, but the worst case is likely ω(n log n) if there are many pairs of points within dmax of each other.)

Point Clustering algorithm

1 Answers