CareerCup

Let P_x be an array of the points sorted by their x-coordinates and P_y an array of the points sorted by their y-coordinates. Divide the plain into two regions e.g. using the median of the x-coordinates. Assume delta is the minimum distance among points entirely in one of the regions (determined by recursion). Now consider the vertical strip centered around the median having width 2 * delta. Let S_y be the sorted subset of P_y consisting of the points in the strip. For each element in S_y calculate its distance to the next 7 points in S_y.

there is O(n^2) approach ,

int minD,X,Y;

simply.. for (x0,y0),traverse through the array.. and calculate the distance from formula
sqrt((y2-y1)^2+(x2-x1)^2),and keep on updating the values of minD and X,Y;

i'm sure there must be better sol. than this .

. pls do correct me if i'm wrong

for each point in x-y plane calculate the distance sqrt(x^2 + y^2) wrt to (0,0) and store them in array. sort the distances in this array. find the index in array with (next position - current position) is minimum. The points corresponding to this min distance are closest.

Question. Were you expected to write the code on the white board for this problem or just outlining the idea was enough?

Here is the solution using the divide & conquer method:
rosettacode.org/wiki/Closest-pair_problem/C

Approach can be solving using O(n^2) approach. calculate distance between every 2 points and find the minimum distance pair.

Or in divide and conquer we can use highest coordinates/2 and divide the plane and keep doing it until we reach a set where we just have 2 points.. for every region calculate dist(min) and dist with its neighboring cells. this might be complicated to implement though.

Let S={(x1,y1), (x2,y2), (x3,y3)....(xn,yn)}
find the mean (X,Y) of all the points say X=x1+x2+x3....xn/n and Y=y1+y2+y3...yn/n
we have actually found the centroid of the set of points. We now need to replace this imaginary point X,Y with a real point. For that:
find the minimum distance of this imaginary point X,Y with a point in the set S. That point is what we are looking for.

Brute-force checking every pair works and easy to implement but inefficient.

Divide and conquer dynamic approach is better. Details are below:

Look for Closest_pair_of_points_problem on Wiki page for quick overview.

Look for "Lecture -9 Divide And Conquer -IV Closest Pair" in youtube - this video lecture is entirely dedicated to explaining the algorithm.

Enjoy!

Calculate distance every point from origin.
Store this value in a new array. Sort this array. Now for every adjacent element find the the one with min(abs(a[i]-a[i+1]))
Timing complexity of this algorithm will be nlogn

Divide and Conquer.