Finding the closest point for each point in the set

Question

I have a set of n points in the form (X,Y) , and I want to find the closest point to each point in the set, and the other point belongs to the same set.

The naive algorithm is simple and O(n^2) , but I want to do something better.

Any help is appreciated.

Answer 1

You only need O (N) time to get the closest point to each point using Delaunay triangulation . Just select the edge with the minimum length starting at each point.

And Delaunay triangulation can be found in O (N log N) time.