4

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.

Aman Deep Gautam
  • 8,091
  • 21
  • 74
  • 130
  • I knew this before but I do not understand how it is working.can you please give some explanation or some link which explains the algorithm. – Aman Deep Gautam Sep 20 '12 at 16:55
  • Moreover I want the closest point for every point so I have to modify that algorithm. – Aman Deep Gautam Sep 20 '12 at 16:57
  • My bad, didn't read carefully. As for your problem, I don't think there is any better way. – nhahtdh Sep 20 '12 at 17:04
  • @nhahtdh I do not understand how this question is duplicate. The author of that question itself has accepted that the approach he used in the question is totally wrong and he wanted to do something different. Moreover none of the answers at that question matches whith the answer to this question. I feel it is totally different. I do not understand why they are claimed as duplicate – Aman Deep Gautam Sep 23 '12 at 22:40

1 Answers1

7

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.

Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98