Closest Pair of Points | Divide and Conquer | GeeksforGeeks

This video is contributed by Harshit Verma

Please Like, Comment and Share the Video among your friends.

Also, Subscribe if you haven't already! :)

[sankeethganeswaran]

the time complexity here isn't optimal. it assumes you're sorting by the y for each recursive call, which is unecessary. you only need to do it once at the start, which makes the recurrence T(n) = 2T(n/2) + O(n) = O(nlogn)

[adamodimattia]

I got lost after 4th minute. The most important part is unintelligible.

[Jack-dxqb]

I'd like to think of the step 6 as follows:

Consider a d by d square fully contained in the right strip. Then there can be at most four points in the square, i.e., the four points all lying on the four vertices of the square, since if there are five points or more, then there will be at least one pair of points whose distance is smaller than d, which is a contradiction. This holds similarly for the left strip as well.

Now, let P be any point in the strip of width 2d centered at the vertical line shown in the video. For any 2d by 2d square containing P and fully contained in the strip, there exists at most eight points. In this worst case, P is at the center of the 2d by 2d square, and the other eight points lie on vertices and the middle of all edges. Thus, it takes only constant time to verify whether there is a point on the other side of P whose distance from P is smaller than d.

The number of points in strip is O(n), and each point takes a constant to verify. So, verifying whether there is a pair of points lying on different sides whose distance is smaller than d takes O(n).

[zankhanabhatt]

How we can arrange the elements on the plane?

[paragggoyal]

i see all these comments saying that very good explanation but i don't think this explanation is good at all my personal opinion.

[futurezing]

Isn't the comparison done for all the points in the strip in stripClosest function rather than just looking at only 7 points? What am I missing?

[oskaerd]

well this is calculating distance between two closest points, not the points themselves. be specific. disappointed

[joaquinp]

Why do i need to compare to other 7 points? Isn't it enough to compare to at most the 4 points that are on the other side of the strip? I mean, if the 2 points that yield the minimum distance are at the same side of the strip, i would have found them before making the strip, when comparing all the points at each side... so i only need to compare a point on the left side with the 4 points of the right side that are at most at d distance, or am i missing something?

[tianchen]

I get confused on 7 points because actually none of the points on your side will be the result because they are all > d. so you only compare to the other 4 points on the other side which is not enough if you try to draw a circle with a radius of d center at your point. It touches more "square" on the other side if you are close to the strip. I think this is very clear to everyone.

[amankhunt]

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

[randythamrin]

02:38 step number three, confuse me? why 12 and 14 are the closest ones, or 15 and 3 are the closest ones for each side, how we calculate it?

[lllegend]

what if the points are (-3, -4), (-2, 4), (-2, -2) for example? wouldn't this be stuck as strip contains the 3 points then you'd solve them recursively only to be stuck again with the same 3 when u check around midpoint

[guodonghu]

I think you guys should try to implment 1D closet pair which is easier to understand. The basic idea behind these is Devide and Conquer. We understand the idea is the most important.
public static int mindist(int[] a, int lo, int hi) {
if (lo >= hi) {
return Integer.MAX_VALUE;
} else if (lo == hi - 1) {
return a[hi] - a[lo];
} else {
int m = lo + (hi - lo) / 2;
int delta_1 = mindist(a, lo, m); // left points set
int delta_2 = mindist(a, m + 1, hi); // right points set
int delta_3 = a[m + 1] - a[m]; // strip points min distance
return _Math.min(delta_1, delta_2, delta_3);
}
}

[pranav]

Those who didn't get the above explanation,
This video might help-

[mikhailurmich]

DnC solves it in O(n logn)
The code is horrible

[RonitJoshi]

Let's say the data set is immense, with over 10^9 values of points. Would it be wise to split the list into 3 instead of 2 and do it accordingly? If so, why can't I split it into 3 parts for smaller data sets as well or even split into 4 or 5?

[seanwalker]

how did you find dl and dr in step 3? and what time complexity did it take?

[amiraliomidfar]

Thanks for your great video. Quick question: According to "Algorithm Design" by Tardos the time complexity is O(nlogn) I didn't get how you derived it to be to O(n(logn)^2). I guess we can't use master theorem in the way you formulated it as the theorem uses big theta and this case we had big O.

[anujdhoot]

I could not understand why 7 points comparison only. How did you use the rectangle geometry also unknown? Request you to stress more on the 7n comparison part as it's not clear. Why you say d/square-root(2) should not be possible. I believe it is less than d and hence minimum. I need more lucid videos on this topic.

[ghilmanfatih]

If this problem is an interview problem, I'll be damned