Click to See Complete Forum and Search --> : Clustering points in a graph


foosball
August 11th, 2009, 09:16 PM
Hello
I have numerous points in a 2-D graph and I need to refine it by dropping points that are too close to each other. ('too close' can be some small distance)
The algorithm I thought of is to iterate through the list of points, find the distance from every other point and then decide to drop it or not, but this takes O(N*N) time where N, the length of the list can be large.

I was wondering whether there is a more efficient algorithm.

Thanks
Bruce