On Jun 25, 10:58 am, amit <[email protected]> wrote:
> Can any one explain how to find the closest pair of points given N
> points in 2-D .
> I have read this in google but i m not able to write pseudocode....
I guess you mean in O(n log n), since the naive O(n^2) algorithm is
just
d = infinity
for all point pairs <p1,p2>
if (dist(p1, p2) < d) { closest = <p1,p2>; d = dist(p1,p2) }
return closest
For the standard divide-and-conquer algorithm, check this.
http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
It's about as clear as it an be.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
