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.