O(n log n) Algorithm for Closest Pair II [Advanced - Optional]
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Universidad de Stanford
Curso 1 de 4 en Algoritmos Programa Especializado
The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).
Algorithms, Randomized Algorithm, Sorting Algorithm, Divide And Conquer Algorithms
A really exciting and challenging course. Loved the way the instructor explained everything with so much detail and precision. Definitely looking forward to the next course in the specialization.
Very good course in algorithms. I bought the book to help me understand but the lectures make it way easier and thus much more fun to understand the analysis. Looking forward to complete the spec
Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.
O(n log n) Algorithm for Counting Inversions I12:35
O(n log n) Algorithm for Counting Inversions II16:33
Strassen's Subcubic Matrix Multiplication Algorithm22:32
O(n log n) Algorithm for Closest Pair I [Advanced - Optional]31:46
O(n log n) Algorithm for Closest Pair II [Advanced - Optional]18:58
Tim Roughgarden
Seleccionar un idiomaAlemán (German)Español (Spanish)Francés (French)Inglés (English)ItalianoPolacoRuso (Russian)VietnamitaptPtÁrabe (Arabic)
Alright. So the plan for this video is to prove the correctness of the divide and conquer closest to pair algorithm that we discussed in the previous video. So just to refresh your memory, how does the outer algorithm work? Well, we're given endpoints in the plane. We begin by sorting them, first by x-coordinate and then by y-coordinate. That takes n log in time. Then we enter the main recursive divide and conquer part of the algorithm. So what do we do? We divide the point set into the left half and the right half, Q and R, then we conquer. We recursively compute the closest pair in the left half of the point set Q. We recursively compute the closest pair in the right half of the point set R. There is a lucky case where the closest pair on the entire point set lies either all on the left or all on the right. In that case, the closest pair is handed to us on a silver platter, by one of the two recursive calls. But there remains the unlucky case where the closest pair is actually split with one point on the left and one point on the right. So to get our N log N running time bound, analogous to Merge Short in our inversion counting, we need to have a linear time implementation of a subroutine which computes the best, the closest pair of points, which is split, one on the left and one on the right. Well, actually, we don't need to do quite that. We need to do something only a little bit weaker. We need a linear time algorithm, which whenever the closest pair in the whole point set is in fact split, then computes that split pair in linear time. So let me now remind you of how that subroutine works. So it has two basic steps. So first, there's a filtering step. So it looks at, first of all, a vertical strip, roughly down the middle of the point set. And it looks at, only at points which fall into that vertical strip. That was a subset of the points that we called S sub Y, 'cause we keep track of them sorted by Y coordinate. And then we do essentially a linear scan through SY. So we go through the points one at a time, and then, for each point, we look at only the almost adjacent points. So for each index I, we look only at J's that are between one and seven positions further to the right, than I. So among all such points, we compare them, we look at their distances. We remember the best such pair of points. And then that's what we return from the count split pair subroutine. So we've already argued, in the previous video, that the overall running time of the algorithm is N log N. And what remains to prove correctness. And we also argued, in the previous video, that correctness boils down to the following correctness claim. In the sense that, if we can prove this claim, then the entire algorithm is correct. So this is what remains. Our residual work is to provide a proof of the correctness claim. What does it say? It says consider any split pair that is one point p from the left side Q, capital Q, and another point little q drawn from the right side of the point set capital R. And fur, further suppose that it's an interesting split pair meaning that the distance between them's at most delta. Here delta is recall the parameter pass to the count split pair subroutine, which is the smallest distance between a pair of points all on the left or all on the right. And this is the only case we're interested in. There's two claims. First of all, for p and q, both members of the split pair survive the filtering step. They make it into the sorted list S sub Y, and second of all, they will be considered by that double for loop, in the sense that the positions of p and q in this array, S sub Y, differ by at most seven. So that's the story so far. Let's move on to the proof. So let's start with part A which is the easy part relatively of the claim. So remember what we start with, our assumptions. We have a point p, let's write it out in terms of the X coordinates, X1 and Y1, which is from the left half of the point set. And we have a point q, which we'll call X2Y2, which comes from the right half of the point set. And furthermore, we're assuming that these points are close to each other. And we're gonna use that hypothesis over and over again. So the Euclidean distance between p and q is no more than this parameter delta. So, first, something very simple, which is that if you have two points that are close in Euclidean distance, then both of their coordinates have to be close to each other, right? If you have two points, and they differ by a lot in one coordinate, then the Euclidean distance is gonna be pretty big as well. So, specifically. By our hypothesis, that p and q have Euclidean distance less than delta, it must be that the difference between their coordinates in absolute value is no more than delta, and as well, the difference between their y-coordinates is at most delta. Okay, and this is easy to see if you'd just return to the definition of Euclidean distance that we reviewed at the beginning of the discussion of closest points. Okay? So if your distance is at most delta, then in each coordinate, you differ by at most delta as well. Now, what does A say? [sound]. So proof of A. So what does part A of the claim assert? It asserts that p and q are both members of SY, are both members of that vertical strip. So another way of saying that is that the X coordinates of p and q, that is, the numbers X1 and X2 both are within delta of Xbar. Remember, Xbar was in some sense the median X coordinate. So the X coordinate of the N over two'th leftmost point. So we're gonna do a proof by picture, so consider, forget about the Y coordinates, that's of irrelevant right now, and just focus on the X coordinates of all of these points. So on the one hand we have X bar. This is the X coordinate of the N over two'th point to the left. And then there are the X coordinates which define the left and the right borders of that vertical strip. Namely Xbar-delta and Xbar+delta. And then somewhere in here are X1 and Y1, the X coordinates of the points we care about, p and q. So a simple observation, so because p comes from the left half of the point set, and Xbar is the rightmost X coordinate of the left half of the point set, the X coordinate is at most Xbar. Right? So all points of Q have X coordinate, at most, Xbar, in particular, p does. Similarly, since Xbar is the rightmost edge of the left half of the point set, everything in the right half of the point set has X coordinate, at least Xbar. So in particular, little q does as well. So what does this mean. So this means x1, wherever it is, has to be at the left of x bar. X2 wherever it is has to be to the right of x bar. What we're trying to prove is that they're wedged in between x bar minus delta and x bar plus delta. And the reason why that's true is because their x coordinates also differ by at most delta. Okay, so what you should imagine is. You can imagine x1 and x2 are sort of people tied by a rope at the waist. And this rope has length delta. So wherever x1 and x2 move, they're at most delta apart. Furthermore x1, we just observed, can't move any farther to the right than Xbar. So even if X1 moves as far to the right as it can, all the way to Xbar, X2, since it's at most delta away, tied by the waist, can't extend beyond X bar+ delta. By the same reasoning, X2 can't move any further to the left than Xbar, X1 being tied to the waist to X2, can never drift further to the left than Xbar minus delta. So that's the proof that X1 and X2 both lie within this region, and that defines the vertical strip. So that's part A. If you have any split pair whose distance between them is less than delta, they both have to wind up, in this vertical strip. And therefore wind up in the filtered set, the proof set, S sub Y. So that's part A of the claim. Let's now move to Part B. Recall what part B asserts. It says that the points p and q, this split pair that are distance only delta apart. Not only do they wind up in this sort of filtered set SY, but in fact, they are almost adjacent in SY, in the sense that the indices in the array differ by, at most, seven positions. And this is a part of the claim that is a little bit shocking. Really what this says is that we're getting away with more or less a variant of our one dimensional algorithm. Remember when we wanted to find the closest pair of points on the line, all we had to do was sort them by their single coordinate and then look at consecutive pairs and return the best of those consecutive pairs. Here what we're saying is really, once we do a suitable filtering focus on points in this vertical strip, then we just go through the points according to their Y coordinate. And okay, we don't just look at adjacent pairs. We look at pairs within seven positions, but still we basically do a linear sweep through the points in SY. According to their Y coordinate and that's sufficient to identify the closest split pair. So why on earth will this be true. So our workhorse in this argument will be a picture which I am going to draw on next. So I'm going to draw eight boxes, which have a height and width delta over two. So here, delta is the same parameter that gets passed to the closest split pair subroutine. And it's also the same delta which we're assuming p and q are closer to each other than, right? So that's, remember, that's one of our hypotheses in this claim. The distance between p and q is strictly less than delta. So we're gonna draw eight delta over two boxes. And they're gonna be centered at x bar. So, this same center of the vertical strip that defines S Y. And the bottom is going to be the smaller of the Y-coordinates of the points p and q. So it might be p, it might be q. It doesn't really matter. But the bottom is going to be the smaller of the two. So the picture then looks as follows. So the center of these collections of eight boxes, X bar, the bottom is the minimum of Y1, Y2. We're gonna have two rows and four columns. And needless to say, we're drawing this picture just for the sake of this correctness proof, right? This picture is just a thought experiment in our head. We're just trying to understand why the algorithm works. The algorithm, of course, does not draw these boxes. The subroutine, the, closest split pair subroutine is just that pseudo code we saw in the previous video. This is just to reason about the behavior of that subroutine. Now looking ahead, I'll make this precise in two lemmas that are about to come up, what's going to be true is the following. So, either p or q is on this bottom line, right? So we define the bottom to be the lower Y coordinate of the two. So maybe, for example, q is the one that has the smaller Y coordinate, in which case, is gonna be, somewhere, say, down here. P, you remember, is from the left half of the point sets. So p is maybe gonna be here or something. And we're gonna argue that both p and q have to be in these boxes. Moreover, we're gonna argue that these boxes are sparsely populated. Every one contains either zero or one point of the array S sub Y. So, what we're gonna see is that there's at most eight points in this picture, two of which are p and q, and therefore, if you look at these points sorted by Y coordinate, it has to be that they're within seven of each other, the difference of indices is no more than seven. So, we're gonna make those two statements precise one at a time by the following two lemmas. Let's start with lemma one. Lemma one is the easy one. And it states that all of the points of S sub Y, which show up in between the Y coordinates of the points we care about p and q have to appear in this picture, they have to lie in one of these eight boxes. So we're going to argue this in two steps. First, we're going to argue that all such points have to have Y coordinates within the relevant range of this picture between the minimum of Y1 and Y2 and delta more than that, and secondly that they have to have X coordinates in the range of this picture, namely between X bar minus delta and X bar plus delta. So let's start with Y coordinates. So again, remember this key hypothesis we have, okay. We're dealing with a split pair p-q that are close to each other. The distance between X and Y is strictly less than delta. So the very first thing we did at the beginning of this proof is we said well, if their Euclidean distance is less than delta then they have to differ by at most delta in both of their coordinates, in particular in their Y coordinate. Now remember whichever is lower of p and q, whichever one has a smaller y coordinate is precisely at the bottom of this diagram. For example, if q is the one with the smaller y coordinate, it might be on the black line right here. So that means in particular x has y coordinate no more than the top part of this diagram. No more than delta bigger than q. And of course all points with Y coordinates in between them are equally well wedged into this picture. So that's why all points of SY with a Y coordinate between those of p and q have to be in the range of this picture, between the minimum of the two Y coordinates and delta more than that. Now what about horizontally? What about the X coordinates? Well this just follows from the definition of S sub Y. So remember, S sub Y are the points that fall into this vertical strip. How did we define the vertical strip? Well it had center Xbar, and then we fattened it by delta on both sides. So just by definition, if you're an SY, you've gotta have X coordinates in the range of this picture. X delta plus minus, sorry, xbar plus minus delta. So that completes the proof of the lemma. So this is not. This is just a lemma. So I'll use a lower case qed. Remember this is just a step toward proving the overall correctness claim. But this is a good step. And again, the way you think about this is it says we draw this boxes. We know that either p or q is at the bottom. The other one is going to be on the other side of the black line x bar but will be in some other box so perhaps maybe p is here and the lemma is saying that all the relevant points of SY have to be somewhere in this picture. Now remember in our double for loop we only search seven positions away, so the concern is that this is a sorta super highly populated collection of eight boxes. That's the concern, but that's not going to be the case and that's exactly what lemma two is going to say. Not only do the points between p and q in Y coordinates show up in this diagram, but there have to be very few. In particular, every box has to be sparse, with population either zero or one. So, let's move on to lemma two. So formally the claim is [sound], we have at most one point of the point set in each of these eight boxes. And this is finally where we use, in a real way, the definition of delta. This is where we finally get the payoff from our realization long ago, that when defining the closest split pair subroutine, we only really need to be correct in the unlucky case. In the case we're not handed the right answer by one of our recursive calls. We're finally gonna use that fact in a fundamental way. So we're gonna proceed by contradiction. So we're going to think about what happens if there are two points in a single box and from that we'll be able to derive a contradiction. So, call the points that wind up in the same box A and B. So, to the contrary, suppose A and B lie in the same box. So, maybe this is A here, and this is B here, at antipodal corners of this particular box. So from this supposition, we have two consequences. First of all. I claim that A and B lie on the same side of the point set. They're either both in the left side, Q or they're both in the right side, R. So why is this true? Well it's because every box lies either entirely on the left half of the point set or on the right half of the point set. Recall how we define x bar. X bar is the x coordinate of the right most point amongst the left half of the point set capital Q. So therefore points with x coordinate at most x bar have to lie inside the left half Q. Points with x coordinates at least x bar have to lie inside the right half of the point set capital R. So that would be like in this example. A and b both lie in a box which is to the right of x bar. So they both have to come in the right half of the point set capital R. This is one place we are using that there are no ties in X coordinate, so if there's a point with X, X coordinate or X bar, we can count it as part of the left half. So every box, by virtue of being either to the left of xbar or to the right of xbar, can only contain points from a common half of the point set. So that's the first consequence of assuming that you have two points in the same box. The second consequence is, because the boxes are small, the points gotta be close. So, if A and B co-habitate a box, how far could they be from each other? Well, the farthest they could be is like I've drawn in the picture, with the points A and B. Where they're at opposite corners of a common box. And then you bust out Pythagorean's Theorem, and what do you get? You get that the distance between them is delta over two, the side of the box times root two. And what's relevant for us is this is strictly less than delta. Okay? But, now, here is where we use, finally, the definition of delta. Consequences one and two in tandem, contradict how we define delta. Remember what delta is. It's as close as two pair of, a pair of points can get if they both lie on the left side of the point set, or if they both lie on the right side of the point set. That is how we defined it. As small as a pair of points on a common half can get to each other. But what have we just done? We've exhibited a pair A and B that lie on the same half of the point set, and are strictly closer than delta. So that contradicts the definition of delta. So that completes the proof of lemma two. Let me just make sure we're all clear on why having proved lemma one and lemma two we're done with the proof part B of the claim and therefore the entire claim because we already proved part one, now a long time ago. So let's interpret the 2 lemmas in the context of our picture that we had all throughout. In terms of the eight boxes of side length delta over two by delta over two. So again, whichever is the lower of p and q, and again let's just for the sake of concreteness say it's q, is at the bottom of the picture. The other point is on the other half of the line Xbar, and is in one of the other boxes. So, for example, maybe p is right here. So lemma one says that every relevant point, every point that survives the filtering and makes it into SY, by virtue of being in the vertical strip, has to be in one of those boxes, okay? If it has Y coordinate in between p and q. Lemma two says that you can only have one point in each of these boxes from the point set, so that's gonna be at most eight total. [sound] So combining them. Lemmas one and two imply, that there are almost eight points in this picture and that includes p and q because they also occupy two of eight boxes. So in the worst case, if this is as densely populated as could possibly be, given lemmas one and two, every other box might have a point and perhaps every one of those points has a Y coordinate between p and q. But this is as bad as it gets. Any point of the strip with Y coordinate between p and q occupies a box. So, at most, there are these six wedged in between them. What does this mean? This means if from q you look seven positions ahead in the array, you are guaranteed to find this point p. So a split pair with distance less than delta is guaranteed to be identified by our double for loop. Looking seven positions ahead in the sorted array SY is sufficient to identify, to look at every conceivably interesting split pair. So that completes the assertion B of the correctness claim and we're done. That establishes that this supremely clever divide and conquer algorithm is indeed a correct O(nlog(n)) algorithm that computes the closest pair of a set of n points in the plane.