Video 5-8: Closest Points in the Plane
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-16, 22:48
The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.
0:04 The last problem in this chapter is another cute application of divide and conquer. And this time let's do a bit more of a geometric problem. Uh it's the closest pair of points in the plane problem. Um it is what the name maybe promises. Uh but formally well first of all for the notation so that you know when it pops up what these things mean and also to keep uh keep a few um conditions side remarks there. We're given an array of points. Now in the plane this means every point has an x and a ycoordinate and think of these points as as little objects if you wish. So p stores references to these objects and then the objects have two fields x and y. uh we'll assume here that these are just real numbers and we'll try to not worry too much about that we cannot really compute with reals. It will eventually not be a problem. Uh but in principle it could be arbitrary numbers for now. The goal is to find the identity of two pairs so of of two points. So the in the initial array there will be two indices I and J so that the corresponding points are closest in uklidian space in uklidian distance.
1:20 Uh uklidian distance is of course the standard distance that you all know. If you write this out here it looks a bit big but it's really just taking the difference in x and the difference in y squaring it adding it up and taking the square root of the whole thing. One point here, one point here. What's their ukidian distance? Pythagoras. We take the difference in x and the difference in y. Then d ^2 is delta x^2 + delta y^2. Solve for d. Now luckily here um if you're just looking for minimizing the distance square root is a monotone function. So uh if some if two points are closer in this actual ukidian distance, they're also closer in the squared uklidian distance. So I can leave off the square root. I'm only comparing distances. The square root never changes the relative order.
2:27 Um we'll we'll use that. That's that's this remark here. Uh we don't really need to compute square roots ever here. the naive solution. Again, you always want to compare a baseline first. Also, hint for exams, if you're asked to design an algorithm, first do the simple and stupid slow thing. Uh that's correct, and then think about how to how to speed it up. I can take every possible pair of points, compute their distance, and just keep the minimal distance.
2:58 Ah um we'll here basically just find the distance of the two closest points. Uh all the algorithms that do that can just as well keep track of the actual two points but the code is a bit easier if you leave that out. So we'll be we'll be happy if you just give me this little d the distance between the closest points with the understanding that you could also report the points uh easily. Uh and the cost model is is just counting arithmetic operations.
3:33 Um so essentially what we need to compute these distances and what else you need. Um again the square roots are not not needed. uh formally you could say we're working on this on a strange special device called the real random access machine where we can work with real numbers so that we don't have to worry about precision. All of this um this is all not really uh important here. Um this is just to be very formally correct. Maybe you want to fix a model of computation. So far we've always worked on on RAM with with a fixed number of bits in the strings in in the uh integers. So you could also do that here.
4:30 that's what I mentioned. We only find the distance. Um let's try to find a faster solution for this using divide and conquer. So again if you have points what could we divide? We could try to cut in half. Uh here's already some some uh random input where uh we have points in the plane given here. They're numbered by their index in this array which is just to kind of uh stress the fact that they are not sorted or anything at the beginning. What we'll do is um a standard trick in such geometric problems and that's why we also covered median of medians in these things. We'll start by finding the median coordinate in x direction so that I can properly split in the first half and the second half points in x direction. So there's some point whose coordinate divides the points in two equally large sets. If I um take the ones left and right of this point, that's the median median coordinate x.
5:35 Then we can try to find um the the smallest distance on the left and on the right and then recombine. And this recombination step is where the cleverness happens.
5:47 Uh but if you think about where can this smallest distance between two points in the input be well it could either be here these two points are closest or maybe it could be here on the right that's a that's b in principle like in this input is a bit hard to imagine but if there were some points here it could also be that the closest points are split by this line that you divide it with. Now the cases A and B are easy because these are done by the recursive call. You're recursively finding in all the left points what are the two that are closest and same for the right. The last part is what you have not found yet because they were not together in any of the recursive calls. You've never compared these two points across this dividing line.
6:44 Okay. And in principle that could be a problem. So um what do we do for these for these uh to find the pairs for part C? Well uh I mean any point pair of part C is one point left one point right. So let's just compare those.
7:14 Now, sadly, this could be just as bad as when we started if the input really conspires against you. Um, where's my worst case? Um, okay.
7:28 Two worst cases. Um, okay. Okay, for this uh the fir first step is if we compare literally everything on the left with everything on the right, that's still a quadratic. We don't want to do that. That's is that clear? So there's n half on the left and half on the right. The product is too much. Um most of the time you don't have to do that. Suppose on the left you found two points that are at distance delta. Then clearly if this point C is the final solution, so there's two points, one left, one right with even closer distance, then these have to be really close to the dividing line. If your input is like this, you're all already done because within delta of the dividing line, there's nothing except for this one one point that defined the dividing line, of course. Okay, I cannot find two points that are closer to each other if they're already further away individually from the dividing line where one is left and one is right. All of these combinations here that you might have, they're clearly further away from each other than delta because this is already delta.
8:53 Okay, so we only have to look close to this dividing line. Unfortunately, this could be all of your input. If someone conspires against you, they could be all like lined up on top of each other and then we haven't won anything. Uh, by the way, the recursion is still well defined because you can say if the points have equal x coordinate, then we break ties by their index in the array or by y-coordinate. Something like this. This is this is fine. But here you would still have to do n squ comparisons or n square over four comparisons. So how do we do better than that? It seems that here comparing this guy and this guy is still a bit wasteful. But how do we know that they're so far apart? Right?
9:42 Uh this is where the the next trick comes in. Um, also points that are too far apart from each other vertically are clearly not needed to be checked. They're that's the the criterion here is that these points are so far apart in y direction. I could have skipped that comparison. But how do I know that I have that I can skip that comparison if the points are just anonymous objects?
10:21 what we can do is sort the points in y direction. So use the order that we had here naturally. Then I maybe I I can hope that um once I compared this this point with a few I can stop because I've already exceeded the threshold. But it might still be that I have to compare this 11 with quite a number of points. Maybe also the 10 with quite a number of points. They can be in y direction in principle can be very close together.
10:54 Uh but if you look at this um a bit carefully, you see that they cannot really be so close together. And what we need here is that delta was the the closest distance between anything on the left and anything on the right was the minimum of the two recursive results. So no two points that are both on the left or both on the right can be closer to each other than delta. And so um within this strip of delta to the left and delta to the right you can have where from from one point here if you go delta distance upwards that's this one you can have at most these eight points that's the precise worst case you can have where you have a point just at distance delta from yourself in x direction and in y direction and another one diagonal and you have the same on the on the right. So here all these points are tight at distance delta. And so I might have to compare this point to these four on the left.
12:08 And uh if I'm if I'm blunt, if I just take all the points that are close enough to this middle and ignore whether they were left or right previously, it's at most eight points that I have to compare any point with.
12:24 Okay. So again, what do we do? We take all the points that are in distance delta around this median. You sort them in y direction and then you do one iteration for each point. You compare it with its eight successors in this sorted list. Once you're done with the next eight, you're already guaranteed to be further away in vertical direction than delta. So you don't need to check. Okay, so the delta comes from the left and the right recursive call that defines you how far you have to go out. In the worst case, it might still be that you have all points here in this strip. that bad case from before.
13:21 This is a real thing. It may happen, but it's not actually costly because after sorting, you would only compare each with eight other things. So after eight n steps, you're done. Still linear in the number of points.
13:39 That's the clever inside of this part. Okay. Uh let me show you this as well a bit. So here are um here's some some random input. Uh let's maybe first jump to where we've already computed the left and right recursive call. So I've I've split my points into left and right. I've recursively found among all the left and all the right points the closest in distance. The closest in distance here are these two yellow points. That defines this little strip where there's a bunch of points in there, but not all that many. Um, and now I have to compare each point with at most eight of the points above it in sorted order. Uh, which here there's only four. So, there's not that much happening.
14:43 And once I checked all of those, I know that all of them are at distance greater than delta. So what remains is the original solution from the right hand side. Um let's start again from the beginning uh to see a bit what the algorithm works like at the start. So I have my points written down twice. I need them both in x direction and in y direction. For the recursion, I need them split by X direction, by X dimension. And then for the strips, I need them by Y direction. That's why we have both arrays. First step is find the median by X. That gives you this split into the the green and yellow points. And they're marked because a point that is to the right of course also needs to be to the right for the recursive problem. So you split this list. Now you go left and in the left recursive sub problem you do the same thing. You again find the the middle recursive go left and so on. Okay. So you split until you have a very narrow part just two points. With two or three points you immediately just compare everything. Compare the two points or compare the three all pairs.
16:04 Then you have uh some closest pair that you have from the right. You go from left, you go to the right, there you get the same. Now when you get back, the minimum distance here was the one from the right. So you have a fairly wide strip that contains all points. And so you have to do compare all of these with each other. In this case, you're doing almost all of the comparisons, but it's only five points in total. And then you come back from there. Okay. Um let's see some more extreme case for this this bad situation that we had before. If we come back from here now you see that really this uh comparison within the strip uh makes a difference. I'm comparing this point here with its eight successors but not more.
17:04 And then I can stop because now I know for sure that I've traveled distance uh more than delta or vertically actually much more here already. You could try to prune it earlier. Okay, almost done. So let's uh let's see what uh the total cost of that is. The recurrence is we have two recursive calls left and right on half the points and uh we need n log n cost for each conquer step because we're sorting all the points in the diagonals in the the this this uh uh vertical strip and in the worst case these are all points so I need n login to combine um this is one of the instances where the master theorem doesn't give you an answer. But Rura's master theorem tells you or you can work it out by just inserting the recurrence. The total time for this is n lo 2n is much much better than los than then n squ the naive method we started with.
18:15 Um but there's one more trick here. We can actually avoid this n login here altogether because think about what we've done. The n login only comes from sorting in each step by the y direction which we have to do for the points that are in the magenta strip. Now it's a bit stupid to sort the same points over and over again. What we should have done is sort once at the beginning and maintain that order throughout. And that's a bit tricky to do but uh it works. So we sort we sort once at the beginning um both by X and by Y. We keep both sorted orders intact. That means we also never have to actually use our median of medians algorithm to find the median. We can just jump into the middle after sorting once. And that gets um all of all of the nlog ends down to linear which then is again the merge sort running time.
19:23 So the final code then looks like this. And this also exists here in the in the animation. You can switch to the version that sorts just once. Um let me briefly demonstrate that here and then we look at the code a bit closer. So I'm I'm sorting the points once by X and Y direction.
19:48 Now I can immediately jump to the median by looking at the half position in in X. Now I have these points sorted. This is the one extra step that we have to worry about. Here are the points sorted by X and sorted by Y. I'm I have to be careful to keep that sorted information for the recursive calls intact. But I can do that by um by passing well the first half and second half of X is already partitioned in the way we need it. And for Y that's why the colors are useful. We have to combine everything that is green and everything that's yellow on one side. So for the left recursive call we only need the greens. So we copy those out but keep the relative order so that among those that are green among those points that are in the left half we still have them sorted by y direct in y direction and the rest is just as we had it.
20:51 So in code you have the the terminating conditions if with just two or three points then um split the median and recurs. That's the part I've I've shown you in the animation and the latter half is exactly as we had it before. Um in code all of the clever argumentation that there's only these eight points in this box and all of that is completely invisible. It's only showing here that I'm in y direction only looking at the next eight points and it magically just works.
21:28 Okay, so if you wanted to analyze this, this all takes constant time. This mark by traverses the points once that's linear time. That's the recursive calls. And then we have another linear contribution from here.
21:48 So overall the the running time is again two recursive calls on half the points and something linear on top that's the merge sort recurrence. So n login total time a bunch of clever tricks combined. Um some observations that are specific to this point problem for example this this strip around the middle and so on. Um others like uh sorting once and passing down the sorted information by by splitting is uh more transferable. This works for other problems as well. And so uh the total time n login is probably uh best possible unless you start uh using the numbers directly and apply some hashing tricks or so on. So on the real RAM this is likely the the limit of what you can do.