CODEWITHSUNDEEP
algorithm
Aman Deep Gautam
Aman Deep Gautam

Reputation: 8737

finding closest point for each point in the set

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

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

Any help is appreciated.

Upvotes: 4

Views: 1116

Answers (1)

Evgeny Kluev
Evgeny Kluev

Reputation: 24647

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

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

Upvotes: 7

Related Questions