Hey,first of all thanks for the amazing explanation!!! I've 1 question: in 3:46you said that we need to check the points lower than the actual point, why is that? How did we already iterate through the higher points? Thanks!
Because we sorted according to y coordinates. The first point we look is the one which is at top, others are all above. And when you go to second point, it is above of others and below of the first point.
First of all i want to say that your explanation is of highest standard, almost in the category of 3Blue1Brown. What i wanted to ask you is do you use python manim lib to animate this?
is there a way to modify this to get all pairs starting from the one of the 2 closest points and ending with the pair of the two furthest apart, i.e. get all pairs sorted by distance
Excellent explanation! I just have one question though. When we get the sets of the points , why did we traverse the ysorted array instead of the xsorted array?
Hi! It seems to me that you did not account the possibility of different points with equal x-coordiantes. It is incorrect to write xsorted_left = xsorted[:n//2], because xsorted[:n//2 + 1] may has the same x-coordiate. And what, for example, should we do if all the points have the same x-coordinate?
This algorithm only reduces the amount of bruteforcing to HALF of a simple brute force approach. So it doesnt save much time. I thought up a much faster approach; the killer in computation time is the square root, the whole pythag part really with the mult, mult, sqroot. So you dont do that. Instead; Brute force the lot, BUT just get the distances x1-x2 and y1-y2, the larger of these I call the simple distance. Very quick because it is just two subtractions. Then the real pythag hypotenuse distance can never be more than 1.41 times the length of the simple distance. Then keep a live track of the lowest simple distance, and any time a new lowest simple distance is found calc a "limit distance" of 1.5 times the simple distance. Any future point pair larger than that cannot possibly be the closest pair. So while the brute force is running; you just compile a short list of any pair where its simple distance is less than the best "limit distance". I wrote some C code and tested this. 100 random distributed points, means 4950 brute force tests (but they are incredibly fast tests now!) And in the majority of cases there were only 10 to 30 pairs that made it into the final list out of 4950 tests! So that has eliminated 99.5 percent of the pairs! Even better, you dont have to do the pythag sqroot etc on all 10 to 20 final pairs. Because you already have the smallest simple distance (and the limit distance) you only need to do the pythag testing on 1 to 7 of the final pairs! The average was around TWO pairs needing to be tested! This algorithm is far quicker than the divide and conquer algorithm in cases where the n (total number of points) is not too large. As an additional tweak, when brute force testing to get the two subtractions x1-x2 and y1-y2, you can abort the second half of the test (y) if the x simple distance is larger than the limit. You would have to run it in hardware and do time trials to see if that makes a significant difference. Depends a lot on array accessing time.
Hello, your solution is interesting if proven right, but it's still in O(n²) time complexity, but the solution presented in the lecture is in O(nlogn), which is way faster for large values of n
In CLRS textbook, it takes 5 pages to explain this, and I just get confused after reading page 1. Your video is so nice, although your speak speed is a bit quick. With 0.75 speed mode, I get so fxcking clear for this algo. thank you so so much!
The two points that you found before can be as close to the middle line as they want, thus there is no contradiction in finding them in the rectangle two delta by delta. Second, in your explanation you omitted something re why one looks below some point. You said “let’s look at this point for example” and then out of blue that something has been processed already above it. Finally, Python sucks.
@@insidecode No. I am saying that the contradiction is due to the definition of the minimal distance, not because "it should have been found before" @6:10. Correct logic is "delta prime is smaller than delta, which contradicts that delta is the minimum distance". You lack a bit of structure in your reasoning which makes it hard to follow. You say six but draw 9. Forget to mention that stripe is sorted according to y coordinates and that the algorithm scans down...etc. Sorry. I shouldn't have been rude. Also, it's easy to show that it can't be more than 7 (+1) which would have made the explanation clearer (divide into 8 squares with sides delta/2 there will be two points inside the square => distance less than delta/sqrt(2) < delta => contradiction) - this is easier to explain and doesn't matter too much. It would then suffice to say that it can be shown that you don't need to scan more than 6 (+1).
Discover the new graph theory algorithms course: inscod.com/graphalgo
🔴
/ \
🔵-🔴
| |
🔴-🔵
Wow, Finally a video that explains very well. This is the best so far, even a novice in programming would understand the logic.
Wow, thanks!
Speak for yourself I still don’t get it 😂
Fix: At 11:20, the generic form starts with aT(n/b) not aT(n/2)
Nicely explained and great animations as well. Good job!
Thanks!
damn man just amazing explanation of this concept I have never found such a clear explanation for closest pairs among million of points.
Thanks a lot
Hey,first of all thanks for the amazing explanation!!!
I've 1 question: in 3:46you said that we need to check the points lower than the actual point, why is that? How did we already iterate through the higher points?
Thanks!
Because we sorted according to y coordinates. The first point we look is the one which is at top, others are all above. And when you go to second point, it is above of others and below of the first point.
I was not able to understand the rectangle part.
First of all i want to say that your explanation is of highest standard, almost in the category of 3Blue1Brown.
What i wanted to ask you is do you use python manim lib to animate this?
Hello, thanks for the compliment, nope, I use PowerPoint
Man you are incredible in all your videos. This the most interpretive content, i have ever watched ❤💖
Thanks a lot for your comment!
Woah that was some good visualization!
i have a feeling the list comprehensions/other things you're wriitng in python will go n^2 anyway
First video I check of yours. I liked it, it's very informative, keep it up!
Thanks a lot! Don't hesitate to watch other ones
I have been asked the same question in Google phone screen. Unfortunately I didn't see your video earlier. Good work.
may someone please let me know how to made the animation or the tool used for the animantaion.
Amazing explanation ! 👏👏
Well explained and the code is very precise and understandable ! Cheers !!!
Thankss
Hey your algorithms are easily explained and optimal too ..thanks man
You're welcome!
The best in topic I found, thank you so much !!
Wonderful explanation 👏
Thanks!
Why do we need to create ysorted_left and ysorted_right if we are using just ysorted for in_band construction
Great explanation and the visualisations helped a lot!
Thanks!
Hi, why cant we take d/2 from both side of mid line?
very clear after watching this.
Thanks for the clear explanation! Amazing vids :)
You're welcome!
Just brilliant! Thank you!
great video man congrats, keep going!
Thanks, very well explained
You're welcome!
is there a way to modify this to get all pairs starting from the one of the 2 closest points and ending with the pair of the two furthest apart, i.e. get all pairs sorted by distance
Nice video, keep up the good work!
Thanks!
Excellent explanation! I just have one question though. When we get the sets of the points , why did we traverse the ysorted array instead of the xsorted array?
Because the band is a vertical strip. Traversing the ysorted traverses the points from top to bottom.
great video, very well explained.
Could please provide information about the best worst and average cases of this algorithm????
thanks for the clear explanation
You're welcome!
Hi! It seems to me that you did not account the possibility of different points with equal x-coordiantes. It is incorrect to write xsorted_left = xsorted[:n//2], because xsorted[:n//2 + 1] may has the same x-coordiate. And what, for example, should we do if all the points have the same x-coordinate?
the best explanation ever
Thankss
how to make such animation videos? what skills needed for this??
Nice explanation
can some one explain what is the meaning of recursif call the fuction to ger dL dan dR.
Just discovered this , channel , neste3ref bik
mor lcovid Insha'Allah ndiro match XD
Nicely explained but i found it tough
thanks a lot bro
You're welcome!
This algorithm only reduces the amount of bruteforcing to HALF of a simple brute force approach. So it doesnt save much time.
I thought up a much faster approach; the killer in computation time is the square root, the whole pythag part really with the mult, mult, sqroot.
So you dont do that.
Instead;
Brute force the lot, BUT just get the distances x1-x2 and y1-y2, the larger of these I call the simple distance. Very quick because it is just two subtractions.
Then the real pythag hypotenuse distance can never be more than 1.41 times the length of the simple distance.
Then keep a live track of the lowest simple distance, and any time a new lowest simple distance is found calc a "limit distance" of 1.5 times the simple distance.
Any future point pair larger than that cannot possibly be the closest pair.
So while the brute force is running; you just compile a short list of any pair where its simple distance is less than the best "limit distance".
I wrote some C code and tested this. 100 random distributed points, means 4950 brute force tests (but they are incredibly fast tests now!) And in the majority of cases there were only 10 to 30 pairs that made it into the final list out of 4950 tests! So that has eliminated 99.5 percent of the pairs!
Even better, you dont have to do the pythag sqroot etc on all 10 to 20 final pairs. Because you already have the smallest simple distance (and the limit distance) you only need to do the pythag testing on 1 to 7 of the final pairs! The average was around TWO pairs needing to be tested!
This algorithm is far quicker than the divide and conquer algorithm in cases where the n (total number of points) is not too large.
As an additional tweak, when brute force testing to get the two subtractions x1-x2 and y1-y2, you can abort the second half of the test (y) if the x simple distance is larger than the limit. You would have to run it in hardware and do time trials to see if that makes a significant difference. Depends a lot on array accessing time.
Hello, your solution is interesting if proven right, but it's still in O(n²) time complexity, but the solution presented in the lecture is in O(nlogn), which is way faster for large values of n
wonderful
Wonderful
How to extend this for points in higher dimensions and with other distance metrics like with L-inf ?
In CLRS textbook, it takes 5 pages to explain this, and I just get confused after reading page 1. Your video is so nice, although your speak speed is a bit quick. With 0.75 speed mode, I get so fxcking clear for this algo. thank you so so much!
ohh you're welcome!
great vid
Wow!
aga aksan yapmaya kasmasan iyi video
The two points that you found before can be as close to the middle line as they want, thus there is no contradiction in finding them in the rectangle two delta by delta. Second, in your explanation you omitted something re why one looks below some point. You said “let’s look at this point for example” and then out of blue that something has been processed already above it. Finally, Python sucks.
Hey I'm interested to discuss your comment point by point. So you're saying that we can find more than 6 points in the two delta by delta rectangle?
@@insidecode No. I am saying that the contradiction is due to the definition of the minimal distance, not because "it should have been found before" @6:10. Correct logic is "delta prime is smaller than delta, which contradicts that delta is the minimum distance". You lack a bit of structure in your reasoning which makes it hard to follow. You say six but draw 9. Forget to mention that stripe is sorted according to y coordinates and that the algorithm scans down...etc. Sorry. I shouldn't have been rude. Also, it's easy to show that it can't be more than 7 (+1) which would have made the explanation clearer (divide into 8 squares with sides delta/2 there will be two points inside the square => distance less than delta/sqrt(2) < delta => contradiction) - this is easier to explain and doesn't matter too much. It would then suffice to say that it can be shown that you don't need to scan more than 6 (+1).
Best video