Given n points in the xy plane, what is the time complexity to find the closest pair?

Question

what is the approach of this question , Is it that first we will traverse all the pairs then find the minimum distance between all the pairs

Answer 1

By divide and conquer

T(n)= 2T(n/2)+O(n)

       = O(nlogn )

here distance between pairs calculate by  ab=squr((ax-bx)^2+(ay-by)^2)

ref : http://www.dcs.gla.ac.uk/~pat/52233/slides/ClosestPoints1x1.pdf