Thank you, this is the first explanation I've seen for why we choose the 7 points in this algorithm. All others I've seen simply take that as an obvious truth, which to me it was not.
15:45 Here starts the proof of the next-7 claim. Thank you so much sir, this is beautiful. Plus i think maybe another way of getting rid of the theta(nlgn) of sorting in the recurrence is to do a preprocessing (of y-cor sorting) beforehand (before the main Closest Pair Problem) so that T(n) and theta(nlgn) sorting time can stand independently, and then the final runtime remains theta(nlgn).
THE BEST EXPLANATION SIR . till O(nlog^2(n)) it was very much clear sir but the redefining of the T(n) itself is somewhat non - intuitive since our T(n) should be telling abt only the Time taken to solve the problem as a whole not taking to consideration the sorting part.
it is up to us how we want to define T(n). Here, within T(n) = O(n log n), we can solve the original problem + some extra stuffs, which means the complexity of the original problem is also O(n log n).
For correctness of we are comparing points sorted by y axis, what if there are 7 points in the other quadrant more than d distance away and 1 point directly underneath which is super close we missed that point and in end gave inaccurate result
Suppose "p" is the current point and "q" is the other point (which is super close and underneath p) and (p,q) is the closest pair. You are right, this pair wont be captured while doing our procedure at "p", but it will be captured when we do our procedure at "q''.
hi, so when you say we can 8 points, the way you numbered the boxes, is it posible to have a valid pair in box 1,2 or 3,4, since they are in the same region? case 3 mentions that the points have to be one on a side, and one on the other, but not both in one side
You will not find a valid pair (i.e., < d) in 1 and 2, because they are on the same side [from the definition of "d"]. But it is possible to have a valid pair in 3 and 4 (because they are on different sides).
@@emilyhuang2759 proof of correctness says the following, just sort all points within the strip with respect to y-coordinate. Then if there is a pair with distance < d, then the second point within the pair comes as either the first, or second, or third, ...or 7th point after the first point within the pair. So, our algorithm will find it.
If there would have been a point in 1,2 boxes then it would have already been the part of shortest pair in left region and same applies to right region.so that is why we will be able to find shortest pair of points from left and right.
I understand that each box can have at most one point but why do we even need to compare 7 since the distance on the left half or right half region is at most d. Why don't we just compare the points between the two regions?
Yes, we can fix a point (on a side) and just compare it with 4 (instead of 7) points on the other side. But these 4 points can be anyone's among the next 7 points (if we sort with respect to Y). So, we might still need to examine the next 7 points. The answer is yes, we can do a bit of optimization here, but the asymptotic time will be the same.
Hi, first of all thank you for the video. I didn't understand why there must be one point each little eight boxes. Why the distance of 2 points must not be less than d over square root of 2? Why is not allowed? What is the definition of d?
"d" is the minimum of d1 and d1, i.e., the shortest distance between all possible pairs, where both points are completely on either the left side or the right side. Now this little boxes are completely within the LEFT or RIGHT side. Note that d/root(2) is the length of the diagonal. Now if there are two points within a square, the distance between them will be at most d/root(2), which is shorter than "d", which contradicts the definition of "d" at the first place.
@@algorithmsbysharmathankach7521 So, if I understand correctly, at first we declared that minimum distance of the two points is d and d/root(2) is less than d thats why 2 points cannot be in the same square boxes. Right? Thank you so much:))
@@kirandwivedi7529 yea, you can optimize a bit (to 4 instead of 7), like we don’t need to compute the distance if both points are on the same side, but there is an associated cost to examine if both points are on the same side. Therefore, over all asymptotic complexity won’t change with such optimizations
Since we are dividing and conquering in the same way as merge-sort, we just interleaved our algorithm with mergesort, so that the sorted list (at every level of merging) comes without extra cost.
For every point we take next 7 points yes but 3 of those 7 will be in the same side as starting point so we can ignore them and check with only 4. Because if those 3 are no way can result in closest point as we already found that by recurring for left
Sure, we can modify the algorithm a bit and reduce the number of distance computations per point to 4 from 7, although the asymptotic complexity remains the same.
this is underrated! the only video by which i could understand the 7 points saga!! thanks a ton!
holy shit I was looking for an understanding of why its 7 points. you are the most clear an concise. thank you
Thank you, this is the first explanation I've seen for why we choose the 7 points in this algorithm. All others I've seen simply take that as an obvious truth, which to me it was not.
wow i was not understanding this a whole day......after seeing your video, i understood it thank you so much sir
i really appreciate to you!!!!!!!!
nobody explain why we can calculate only 7 times when the case 3(in your lecture), but you.... so thank you!!
15:45 Here starts the proof of the next-7 claim. Thank you so much sir, this is beautiful. Plus i think maybe another way of getting rid of the theta(nlgn) of sorting in the recurrence is to do a preprocessing (of y-cor sorting) beforehand (before the main Closest Pair Problem) so that T(n) and theta(nlgn) sorting time can stand independently, and then the final runtime remains theta(nlgn).
YES, correct !!!
thanks dear, thinking of the same how to get rid of extra logn factor by not redefining the way sir did ..
You are the only one makes me understand!Thank you!
Thanks you, best explanation of this I have seen so far
Wow! That was a clear and easy to understand explanation. Thank you.
Ur explanation is better than gfg.... Looking forward for more explanations
Thank you sir very nice explanation !!! lockdown ka bharpur fayda uthaya he sir ne
Thank you sir, finally understood it thanks to you.
Great explanation of this problem. Thank you for your work :)
Amazing Explaination Sir!!
thank you so much this helped a lot!!!
THE BEST EXPLANATION SIR . till O(nlog^2(n)) it was very much clear sir but the redefining of the T(n) itself is somewhat non - intuitive since our T(n) should be telling abt only the Time taken to solve the problem as a whole not taking to consideration the sorting part.
it is up to us how we want to define T(n). Here, within T(n) = O(n log n), we can solve the original problem + some extra stuffs, which means the complexity of the original problem is also O(n log n).
Absolutely goated explanation
Really nice explanation! Thank You!
very very well explanation....
great explanation. simple and understandable. thanks a lot
Well explained.. 👏
good explanation
Very well explained !!
Very good explanation
Thank you, this video helped me fully understand!!
For correctness of we are comparing points sorted by y axis, what if there are 7 points in the other quadrant more than d distance away and 1 point directly underneath which is super close we missed that point and in end gave inaccurate result
Suppose "p" is the current point and "q" is the other point (which is super close and underneath p) and (p,q) is the closest pair. You are right, this pair wont be captured while doing our procedure at "p", but it will be captured when we do our procedure at "q''.
@@algorithmsbysharmathankach7521 we take a look at next 7 points right and not the ones that are already scanned
@@algorithmsbysharmathankach7521 the points are sorted by y co ordinate and we check with next 7 points not previous ones
Thank you! Great Explanation
really nice explanation
this is great! thank you! why don't professors explain in a similar manner instead of showing 20 slides for 40 min...
Sir..can you please take a class on Dixon's factorization?
hi, so when you say we can 8 points, the way you numbered the boxes, is it posible to have a valid pair in box 1,2 or 3,4, since they are in the same region?
case 3 mentions that the points have to be one on a side, and one on the other, but not both in one side
You will not find a valid pair (i.e., < d) in 1 and 2, because they are on the same side [from the definition of "d"]. But it is possible to have a valid pair in 3 and 4 (because they are on different sides).
Oh, so is the proof of correctness just saying there won't be a point closer to the point than what we find in the third region?
@@emilyhuang2759 proof of correctness says the following, just sort all points within the strip with respect to y-coordinate. Then if there is a pair with distance < d, then the second point within the pair comes as either the first, or second, or third, ...or 7th point after the first point within the pair. So, our algorithm will find it.
If there would have been a point in 1,2 boxes then it would have already been the part of shortest pair in left region and same applies to right region.so that is why we will be able to find shortest pair of points from left and right.
The array in case 3 has all of the points within 2d region. One thing I can't catch up is where the points within 2d x d region come from?
I understand that each box can have at most one point but why do we even need to compare 7 since the distance on the left half or right half region is at most d. Why don't we just compare the points between the two regions?
Yes, we can fix a point (on a side) and just compare it with 4 (instead of 7) points on the other side. But these 4 points can be anyone's among the next 7 points (if we sort with respect to Y). So, we might still need to examine the next 7 points. The answer is yes, we can do a bit of optimization here, but the asymptotic time will be the same.
Hi, first of all thank you for the video.
I didn't understand why there must be one point each little eight boxes. Why the distance of 2 points must not be less than d over square root of 2? Why is not allowed? What is the definition of d?
"d" is the minimum of d1 and d1, i.e., the shortest distance between all possible pairs, where both points are completely on either the left side or the right side. Now this little boxes are completely within the LEFT or RIGHT side. Note that d/root(2) is the length of the diagonal. Now if there are two points within a square, the distance between them will be at most d/root(2), which is shorter than "d", which contradicts the definition of "d" at the first place.
@@algorithmsbysharmathankach7521 So, if I understand correctly, at first we declared that minimum distance of the two points is d and d/root(2) is less than d thats why 2 points cannot be in the same square boxes. Right? Thank you so much:))
@@timeinabottle9155 The min distance of 2 points that are completely within one side (left or right), which is computed via recursion.
well explained !!
Thank You.
Can anyone explain why the x coordinate was not sorted ?
thank you so much!
made it so clear
thank u :) nice explain
Thank you beast
Thankyou for such good explanation sir,d/2 approach was awesome.
But sir instead of taking 7 points,after visualisation I think only 3 points distance need to be calculated? Where I am going wrong??
@@kirandwivedi7529 yea, you can optimize a bit (to 4 instead of 7), like we don’t need to compute the distance if both points are on the same side, but there is an associated cost to examine if both points are on the same side. Therefore, over all asymptotic complexity won’t change with such optimizations
Dhanyawad guru ji
Thank you sir for the lecture.
😀
Thanks a lot
Perfect
I didn't get how the time complexity is reduced from nlog^2n to nlogn
Since we are dividing and conquering in the same way as merge-sort, we just interleaved our algorithm with mergesort, so that the sorted list (at every level of merging) comes without extra cost.
For every point we take next 7 points yes but 3 of those 7 will be in the same side as starting point so we can ignore them and check with only 4. Because if those 3 are no way can result in closest point as we already found that by recurring for left
Sure, we can modify the algorithm a bit and reduce the number of distance computations per point to 4 from 7, although the asymptotic complexity remains the same.
nice thank you
❤🔥
why it is 7
its clear in the proof, there are 8 boxes, so if we fix one box for one point, they we have other 7 possible boxes for the other point
@@algorithmsbysharmathankach7521 it should be 4 rather than 7
why only 7?
watch from 17:30 to 20:00
tşk
Hit me like if you also didn't understand after 8 boxes.