Closest Pair of Points | Divide and Conquer | GeeksforGeeks
Vložit
- čas přidán 9. 07. 2024
- Find Complete Code at GeeksforGeeks Article: www.geeksforgeeks.org/closest-...
This video is contributed by Harshit Verma
Please Like, Comment and Share the Video among your friends.
Also, Subscribe if you haven't already! :)
God will understand
0:13
I got lost after 4th minute. The most important part is unintelligible.
I admit that one is so hard to understand. But his explanation is the clearest explanation I've ever found so far.
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).
thanks for this dude
sound quality should be improved
My right ear enjoyed it xD
Same, but now I gotta teach my left year wtf I just watched
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?
In stripClosest() ith loop will run for all the point but jth loop should compare 1 point with next 7 points only and so on. Not very clear how he implemented it in the code.
@@sourabroy7787 the j loop will stop when the y- distance becomes greater than d and within that range i.e the starting point and the last point within y distance less than equal to d there can be at most 7 points as explained in the video
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.
Awesome Harshit , started to see some complex problems being taken care by geeks for geeks team now . kudos , I break my head to understand the strip ( how to calculate only required points not all of them in strip, couple of years ago ) this lucid explanation definitely deserves more likes . first from me :) . Keep doing good work . - Sunny
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);
}
}
Thanks a lot!! Does it works for 1D ? Please help I have an exam tomorrow.
I absolutely love the sound quality , Its just fukin amazing !
i know I am kinda off topic but does anybody know of a good website to watch new series online ?
At least explain the code properly.
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.
The recurrence relation is T(n) = 2T(n/2) + Cn
The nlogn part will not come in recurrence because it is one time sorting (Pre processing)
If you solve above recurrence relation you will get O(nlogn)
@@aniketjadhav5473 What do you mean one-time sorting(pre-processing)?? I don't understand. Please clarify.
@@adithyapvarma8738 in the videos implementation the time complexity is nlog^2(n) because on every recursive call we sort strip which is an nlogn step.
the recurrence is then t(n) = 2t(n/2) + O(nlogn). which is O( nlog^2(n))
clearly if we dont have to sort strip on every call we can get O(nlogn) solution.
what aniket is saying is that in order to implement this we have to pre process the points such that we already have a list of the points sorted by y, which we can then use to create strip on every recursive call.
Implementation for this can be found on geeks for geeks website
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?
*Wonderful code, God bless! As my Indian friends say: "Hats off, sir!"*
You can turn on the subtitle
T(n) = 2T(n/2) + O(n) + O(n) + O(n)
T(n) = 2T(n/2) + O(n)
T(n) = T(nLogn)
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?
As you can see divide and conquer is like creating binary tree. If you search online about how performance differs when instead of using binary tree, we use 3-way/4-way tree, there are calculation to prove that binary tree gives better performance compared to others.
my right ear enjoyed this.
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)
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
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?
Very useful contents.thank u👍
thanks for creating these videos
how did you find dl and dr in step 3? and what time complexity did it take?
With the use of brute force....means as soon as the recursion will have n
in the stripClosest() method, the most outer for, shouldn't it be
for( int i = 0; i < size - 1; i++) ?
because when i = size - 1, J = i + 1 which is equals to size, strip[J] would result an error wouldn't it?
please tell me if i'm missing something
Martin D Putra first condition of the inner loop is j< size, it does not matter wherher j is bigger than i or not, it would not iterate while j is equal to size
if you are wondering how can there be a finite number of points (8) from which we need to compute distances, here's an explanation in simplest words.
I've had way too much free time during this quarantine. Here's the explanation of what you wanted with proof.
Once you've found out the LD(minimum distance on the left side of the separator line L) and RD(...........right side of..........), you'd find delta which is the minimum of the aforementioned distances(DELTA=min(LD,RD)). Now, its time for finding the distance b/w the points lying on the EITHER SIDE of the line L. So you'd now construct the strip (of length 2*Delta) across L and search for the points lying within the strip and distanced < DELTA.
We will now build a square(assume its either on the left or right side of the line L just for simplicity) with side=DELTA and see how many points fit in it conforming to our requirement that minD
yes guys I am sitting to your right
Those who didn't get the above explanation,
This video might help-
czcams.com/video/xi-WF07rAQw/video.html (from 20:00)
way better explaination thankyou!
code doesnt seem to compile for C++
Great video! Pan the sound to the center tho pls
Yeah. I thought my earphones started malfunctioning in between. It's so much irritating if the sound is on one side only.
How we can arrange the elements on the plane?
Guess in terms of x index and then y index using a custom comparator?
idk
what about farthest pair of point???
it would have been found recursively
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.
Combine sounds please
will that points diagram will be given?
Where you use |pq| formula
dist(p1,p2)
My left ear: 😐😐
HER HER HER OMG -_- -_-
thankyou. pretty clear explanation
Although your channel and videos are great, you have to work hard on your English or at least speak much slower. Or at super-least, add the textual transcription of the text you say. It's very hard to understand the speech now unfortunately.
Otherwise you're doing a great teaching work, keep on!
Thanks dmitryWeirdo for the appreciation.
We almost always add the subtitles to our videos. You can turn them on using the Subtitles/Captions button in the player settings.
For what it's worth, I feel you did a fantastic job explaining and I am a native English speaker. I had no problems understanding you. Great videos!
@@DBCatch22x Although most of the video is indeed understandable some sections such as a couple seconds into (7:49) would be hard to decipher.
@dmitryWeirdo This video is contributed by an Indian. We are not native English speakers like you. If you are asked to explain something in Hindi, people will probably laugh at you.
amazing
If this problem is an interview problem, I'll be damned
DnC solves it in O(n logn)
The code is horrible
i see all these comments saying that very good explanation but i don't think this explanation is good at all my personal opinion.
Supari nikal K baat kr re baba
Sound in only one ear. Fix It.
problrm is there in the balancing otherwise sound is coming from both the earplugs!!
😂i thought that some problem occured in my earphone until i saw your comment lol...
Evlo try panalum ninga solratha purinjika mudila😑😑😑😑
well this is calculating distance between two closest points, not the points themselves. be specific. disappointed
I did not understand your English accent. It was wired
can u please be louder or else use mic please
Please, reduce your accent, it's unreal to understand some words clearly. i can't watch video properly!
This guy is cooked, doesn't even make sense in the optimization part...
Why is this taught by a telephone scammer?
Cause scammers are smart unlike you.
Horrible accent. Half of the video is unintelligible
Come ooon! I can't understand what this guy is talking about, his speech is bad! AAAAAAAAAAAAA!
Can you explain something in Hindi perfectly? If you can't, don't blame him. He is a native Hindi speaker and he'll improve with time.