So in this video and the next, we’re gonna

study a very cool divide and conquer algorithm for the closest pair problem.

This is a problem where you’re given N points in the plane, and you wanna figure

out which pair of points are closest to each other. So this’ll be the first taste

we get of an application in computational geometry, which is the part of algorithms

which studies how to reason and manipulate geometric objects. So those algorithms are

important in, among other areas, robotics, computer vision, and computer graphics. So

this is relatively advanced material. It’s a bit more difficult. Than the other

applications of divide and conquer that we’ve seen. The algorithm is a little bit

tricky and it has a quite nontrivial proof of correctness. So just be ready for that.

And also be warned that because it’s more advanced. I’m gonna talk about the

material at a slightly faster phase than I do in most of the other videos. So let’s

begin now by defining the problem formally. So we’re given as input N points

in the plain. So each one just defined by its X coordinate and its Y coordinate. And

when we talk about the distance between two points in this problem, we’re gonna

focus on Euclidean distance. So, let me remind you what that is briefly. But we’ll

introduce some simple notation for that, which we’ll use for the rest of the

lecture. So we’re just gonna note the Euclidean distance between two points, PI

and PJ, by D of PI-PJ. So in terms of the X and Y coordinate of these two points, we

just look at the squared differences in each coordinate, sum them up, and take the

square root. Now as the name of the problem would suggest, the goal is to

identify among all pairs the points that pair which has the smallest distance

between them. Next, let’s start getting a feel for the problem by making some

preliminary observations. First, I wanna make an assumption, purely for

convenience, that there’s no ties. So that is, I’m gonna assume all N points have

distinct X coordinates. And also, all N points have distinct Y coordinates. It’s

not difficult to extend the algorithm to accommodate ties. I’ll leave it to you to

think about how to do that. So next, let’s draw some parallels with the problem of

counting inversions, which was an earlier application of divide and conquer that we

saw. The first parallel I wanna point out is that if we’re comfortable with a

quadratic time algorithm, then this is not a hard problem. We can simply solve this

by brute force search. And again, by brute force search, I just mean we set up a

double four loop, which iterates over all distinct pairs of points, to compute the

distance for each such pair. And we remember the smallest. That’s clearly a

correct algorithm. It has to iterate over a quadratic number of pairs, so it’s

running time in gonna be, theta of N squared. And, as always, the question is,

can we apply some algorithmic ingenuity to do better? Can we have a better algorithm

than this naive one which iterates over all pairs of points. You might have a, an

initial instinct that, because the problem asks about a quadratic number of different

objects, perhaps we fundamentally need to do quadratic work. But again, recall back

in counting inversions, using divide and conquer, we were able to get an N log N

algorithm, despite the fact that there might be as many as a quadratic number of

inversions in an array. So the question is, can we do something similar here for

the closest pair problem. Now, one of the keys to getting an N log N time algorithm

for counting inversions was to leverage a sorting subroutine. Recall that we

piggybacked on Merge Short to count the number of inversions in N log at a time.

So the question is, here, with the closest pair, perhaps sorting again can be useful

in some way. To beat the quadratic barrier. So to develop some evidence that

sorting will, indeed help us, compute the closest pair of points in better than

quadratic time, let’s look at a special case of the problem, really, an easier

version of the problem. Which is when the points are just in one dimension. So on

the line, rather than in two dimensions in the plane. So in the 1d version, all of

the points just lie on a line like this one and we’re given the points in some

arbitrary order, not necessarily in the sorted order. So a way to solve the

closest pair problem in one dimension is to simply sort the points and then of

course the closest pair better be adjacent in this ordering so you just iterate

through the n-1 consecutive pairs and see which one is closest to each other. So

more formally, here’s how you solve the one dimensional version of the problem.

You sort the points according to their only coordinate, because you’ve got to

remember, this is only one dimension. So as we’ve seen, using merge sort, we can

sort the points in [inaudible] time. And then we just do a scan through the points,

so this takes linear time. And for each consecutive pair, we compute their

distance and we remember the smallest of those consecutive pairs and we return

that. That’s got to be the closest pair. So in this picture on the right, I’m just

going to circle here in green, the closest pair of points. So this is something we

discover by sorting and then doing a linear scan. Now needless to say, this

isn’t directly useful. This is not the problem I started out with. We wanted to

find the closest pair among points in the plane, not points on the line. But I want

to point out that this, even on the line, there are a quadratic number of different

pairs, so brute force search is still a quadratic time algorithm, even in the 1D

case. So at least with one dimension, we can use sorting, piggyback on it to beat

the naive brute force search bound and solve the problem and N log it in time. So

our goal for this lecture is going to be to devise an equally good algorithm for

the two dimensional case. So we want to solve closest pair of points on the plane,

again, and log N time. So you will succeed in this goal, I’m gonna to show you an in,

log in, time out rhythm for 2D closer spirits. It’s gonna take us a couple

steps, we only begin with a high level approach. Right. So the first I’d even try

is to just copy what worked for us in the one dimensional case. So the one

dimensional case we first sorted the points by their coordinate, and that was

really useful. Now, in the 2D case, points have two coordinates, X coordinates and Y

coordinates, so there’s two ways to sort them. So let’s just sort them both ways.

That is the first tip of our algorithm, which you should really think of as a

preprocessing step. We’re gonna take the input points. We invoke Merge Short once

to sort them according to X coordinate, that’s one copy of the points. Then we

make a second copy of the points, which are sorted by Y coordinate. So we’re gonna

call those copies of points PX, that’s an array of the points sorted by X

coordinate. And PY for them sorted by Y coordinate. Now we know, Merge Short takes

N log N times for the preprocessing step. Only takes O of N log in time. And again,

given that we’re shooting for an algorithm with a running time Big O on N log N. Why

not sort the points? We don’t even know how we’re going to use this factor right

now. But it’s sort of harmless. It’s not going to affect our goal of getting a big

of O and log in time out algorithm. And indeed this illustrates a broader point

which is one of the themes of this course. So recall, I hope one of the things you

take away from this course if a sense for what are the four free parimatives? What

are manipulations or operations you can do on data which basically are costless.

Meaning that if your dataset fits in the main memory of your computer, you can

basically invoke the primitive and it’s just gonna run blazingly fast and you can

just do it even if you don’t know why. And again, sorting is the canonical for free

primitive, although we’ll see some more. Later in the course. And so here we’re

using exactly that principle. So we don’t even understand why yet. We might want the

points to be sorted. It just seems like it’s probably gonna be useful. Motivated

by the 1D case. So let’s go ahead and make assorted copies of the points my X and Y

up front. So reasoning by analogy with the [inaudible] case suggests that sorting the

points might be useful. But we can’t carry this analogy too far. So in particular,

we’re not gonna be able to get away with just a simple linear scan through these

arrays to identify the closest pair of points. So to see that, consider the

following example. So we’re gonna look at a point set which has six points. There’s

going to be two points, which I’ll put in blue. Which are very close in X

coordinate, but very far away in Y coordinate. And then, there’s gonna be

another pair of points, which I’ll do in green. Which are very close in Y

coordinate, but very far away in X coordinate. And then there is going to be

a red pair of points. Which are not too far away in either the x coordinate. Or

the Y coordinate. So in this set of six points, the closest pair is the pair of

red points. They’re not even gonna show up consecutively in either of the two arrays,

right? So in the array that’s sort of by X coordinate, this blue point here is going

to be wedged in between the two red points, they won’t be consecutive. And

similarly, in the, in PY, which is sorted by a Y coordinate, this green point’s

gonna be wedged between the two red points. So you won’t even notice these red

points if you just do a linear scan through PX and P, or PY, and look at the

consecutive pairs of points. So following our preprocessing step, where you just

invert, invoke Merge Short twice, we’re gonna do a quite non-trivial. Divide and

conquer algorithms that can beat the closest pair. So really, in this

algorithm, we’re applying the divide and conquer algorithm twice. First, internal

to the sorting subroutine. Assuming that we use the [inaudible] algorithm to sort,

divide and conquers being used there to get an N log in running time, in this

preprocessing step. And then we’re gonna use it again on the sorted arrays in a new

way. That’s what I’m gonna tell you about next. So let’s just briefly review the

divide and conquer algorithm design paradigm before we apply it to the closest

pair problem. So, as usual, the first step is to figure out a way to divide your

problem into smaller sub problems. Sometimes this has a reasonable amount of

ingenuity, but it’s not going to here in the closest pair problem. We’re going to

proceed exactly as we did in Merge Short in counting inversions problems, where we

took the array, and broke it into it’s left and right half. So here we’re gonna

take the input point set, and again, just recurse on the left half of the points,

and rescurse on the right half of the points, where hereby left and right, I

mean with respect to the points X coordinates. There’s pretty much never any

ingenuity in the conquer step. That just means you take the sub-problems you

identified in the first step and you solve them recursively. That’s what we’ll do

here. We’ll recursively compute the closest pair in the left half of the

points, and the closest pair in the right half of the points. So where all the

creativity in divide and conquer algorithms lie, is in the combined step.

Given solutions to your sub-problems, how do you somehow recover a solution to the

original problem, the one you actually care about? So for closest pair, the

question’s gonna be, given that you’ve computed the closest pair on the left half

of the points, the closest pair on the right half of the points, how do you then

quickly recover the closest pair from the whole. Point set. That’s a tricky problem.

That’s what we’re going to spend most of our time on. So let’s make this divide and

conquer approach for closest pair a little bit more precise. So let’s now actually

start spelling our, our closest pair algorithm. The input we’re given, it’s,

this follows the preprocessing steps. You’ll recall that we invoked merge sort,

twice, we get our two sorted copies of the point set PX, sorted by X coordinate, and

PY sorted by Y coordinate. So the first dividend is the division step. So given

that we have the copy of the points [inaudible] x of the x coordinate. It’s

easy to identify that left most part of the points goes with these. Those n over

two smallest x coordinates. And then the right half will be n over two largest x

coordinates. We’re gonna call those u and r [inaudible]. One thing I’m skipping over

is the base case, I’m not going to bother writing that down. So base case omitted.

But it’s what you would think it would be. So basically, once you have a small number

of points, say, two points or three points, then you can just solve the

problem in constant time by brute force search. You just look at all the pairs,

and you return the closest pair. So, think of it as being at least four points in the

input. Now, in order to [inaudible] to call [inaudible] again on the left and

right half?s, we need sorted versions of Q and R both by X coordinates and by Y

coordinates. So we’re just going to form those by doing suitable linear scans

through PX and PY. So one thing I encourage you to think through carefully

or maybe even code up. After the video is, how would you, form QX, QY, RX and RY,

given that you already have PX and PY. And if you think about it, because PX and PY

are already sorted, just producing these sorted sub lists takes linear. It’s, in

some sense, the opposite of the merge subroutine we used in Merge Short. Here,

we’re sort of splitting rather than merging. But again, this can be done in

linear time. That’s something you should think through carefully later. So that’s

the division step. Now we just conquer, meaning we recursively call closest pair

on each of the two sub-problems. So when we invoke, closest pair on the left half

of the points on Q, we’re going to get back what are indeed the closest pair of

points amongst those in Q. So we’re gonna call those P1 and PQ. So among all pairs

of points that both lie in Q, P1 and Q1 minimize the distance between them.

Similarly, we’re gonna call P2 Q2, the results of the second reversive call is P2

and Q2 are amongst all pairs of points that both lie in R, the pair that has the

minimum Euclidian distance. Now conceptually there’s two cases. There’s a

lucky case and there’s an unlucky case. In the original point set P, if we’re lucky,

the closet pair of points in all of P. Actually both of them lie in queue. Or

both of them lie in R, in this lucky case we’d already be done, if the closest pair

in the entire point set. They happen to both lie in q then this first [inaudible]

is going to recover them and we just have them in our hands: p1, q1. Similarly if

both, of the closest pair of points in all of p lies in the right side, in r. Then

they get handed to us on a silver platter by the second recursive call, that just

operates on R. So in the unlucky case, the closest pair of points in P happens to be

split. That is, one of the points lies in the left half in Q, and the other point

lies in the right half in R. Notice if the closest pair of points in all of P is

split, is half in Q and half in R. Neither recursive call is going to find it, okay.

The pair of points is not past to either of the two recursive calls, so there’s no

way it’s going to be returned to us, okay. So we have not identified the closest

pair. After these two recursive calls, if the closest pair happens to be split. This

is exactly analogous to what happened when we were counting inversions. The recursive

call on the left half of the array counted the left inversions, the recursive call on

the right half of the array counted the right inversions. But we still had to

count the split inversions. So, in this closest pair algorithm, we still need a

special purpose sub-routine that computes the closest pair for the case in which it

is split, and which is one point in q and one point in r. So, just like in counting

inversions, I’m gonna write down that subroutine, I’m gonna leave it

unimplemented for now. We’ll figure out how to implement it quickly. In the rest

of the lecture. Now, if we have a correct implementation of closest split pair. So

that takes, us, input the original point set, set up an X and Y coordinate, and

returns the smallest pair that’s split. Or one point’s in Q and one point’s in R,

then we’re done. So then the split, then the closest pair has to either be on the

left or on the right, or it has to be split. Steps two through four compute the

closest pair in each of those categories. So those are the only possible candidates

for the closest pair, and we just return the best of them. So that’s an argument

for Y, if we have a correct implementation of the closest split pair subroutine, then

that implies a correct implementation of closest. Now, what about the running time?

So the running time of the closest pair algorithm is going to be, in part,

determined by the running time of closest split pair. So on the next quiz, I want

you to think about what kind of running time we should be shooting for with the

closest split pair subroutine. So, the correct response to this quiz is the

second one. And, the reasoning is just by analogy with our previous algorithms for

Merge Short and for counting inversions. So what is all of the work that we would

do in this algorithm? Well, we do have this preprocessing step we call Merge

Short twice. We know that’s N log N. So we’re not gonna have a running time better

than N log N, ’cause we sort at the beginning. And then we have a recursive

algorithm with the following flavor. It makes two recursive calls. Each recursive

call is on a problem of exactly half the size, with half the points of the original

one. And outside of the recursive calls, by assumption, by, in the problem, we do a

linear amount of work in computing the closest split pair. So. With the exact

same [inaudible] tree which proves an N log inbound for merge short, proves an N

log inbound for how much work we do after the pre-processing step. So that gives us

an overall running time bound of N log N. Remember, that’s what we were shooting

for. We were working N log N already to solve the one dimensional version of

closest pair. And the goal of these lectures is to have an M-log in algorithm

for the 2D version so this would be great, in other words, the goal should be to have

a correct. Linear time implementation of the closest split pair, subroutine. If we

can do that, we’re home free. We get the desired in log and out algorithm. Now I am

gonna proceed in a little bit to show you how to implement closest with pair but

before I do that I want to point out one subtle but. Key idea which is going to

allow us to get this linear time correct implementation. So let me just put that on

the slide. So the key idea is that we don’t actually need a full blown correct

implementation of the closest split pair subroutine. So I’m not actually going to

show you a linear time subroutine that always correctly computes the closest

split pair of a point set. The reason I’m not going to do that, is, that’s actually

a strictly harder problem. Than what we need to have a correct recursive algorithm

we do not actually need a sub routine that for every point set always correctly

computes. The closest with a pair of points. Remember there’s a lucky case and

an unlucky case. The lucky case is where the closest pair in the whole points at P

happens, to lie entirely in the left half of the points Q. Or in the right half of

the point R. In that lucky case, we, one of our recursive calls will identify this

closest pair and hand it over to us on a silver platter. We could care less about

the split pairs in that case. We get the right answer without even looking at the

split pairs. Now there’s this unlucky case where the split pair happens to be the

closest pair of points. That is when we need this linear concept routine and only.

Then, only in the unlucky case where the closest pair of points happens to be

split. Now that’s in some sense a fairly trivial observation but there’s a lot of

ingenuity here in figuring out how to use that observation. The fact that we only

need to solve a strictly easier problem. And that will enable the linear time

implementation that I’m going to show you next. So now let’s rewrite the high level

recursive algorithm slightly to make use of this observation that the closest split

pair sub-routine only has to operate correctly in the regime of the unlucky

case when, in fact, the closest split pair is closer than the result of either

recursive call. So I’ve erased the previous steps four and five that, and,

but we’re going to rewrite them in a second. So before we evoke closest split

pair, what we’re going to do is we’re going to see how well did our recursive

calls do. That is, we’re going to define a parameter, little delta. Which is going to

be the closest pair that we found, or the distance to the closest pair we found by

either recursive call. So the minimum of the distance between P1 and Q1, the

closest pair that lies entirely on the left, and P2-Q2, the closest pair that

lies entirely on the right. Now, we’re going to pass this Delta information as a

parameter into our closest split pair subroutine. We’re gonna have to see why on

Earth that would be useful. I still owe you that information. But, for now, we’re

just gonna pass delta as a parameter for use in closest split pair. And then as

before, we just do a comparison between the three candidate closest pairs and

return the best of the, of the trio. So just we’re all clear on where things

stand. So what remains is to describe the [inaudible] of closest with pair. Before I

describe it. Let me be just crystal clear on what it is that we’re going to demand

of the [inaudible]. What do we mean to have a correct and [inaudible] login time

closest to [inaudible]. Well as you saw on the quiz, we want the running time to be O

of N always. And for correctness, what do we need? Again, we don’t need it to always

compute the closest split pair, but we need it to compute the closest split pair

in the event that there’s a split pair of distance strictly less than delta,

strictly better than the outcome of either recursive call. So now that we’re clear on

what we want, let’s go ahead and go through the pseudo-code for this closest

split pair subroutine. And I’m gonna tell you up front. It’s gonna be fairly

straightforward to figure out that this subroutine runs in linear time, O event

time. The correctness requirement of closest split pair will be highly non

obvious. In fact, after I show you this pseudo-code, you’re not gonna believe me.

You’re gonna look at the pseudo-code, and you’re gonna be, like, what are you

talking about? But in the second video on the closest [inaudible] lecture, we will

in fact show that this is, a correct subroutine. So how’s it work? Well, let’s

look at a point set. So the first thing we’re going to do is a filtering step.

We’re going to prune a bunch of the points away and sort of zoom in on a subset of

the points. And the subset of the points we’re going to look at is those that lie

in a vertical strip which is roughly centered in the middle of the point set.

So here’s what I mean. By centered I mean we’re going to look at the middle X

coordinate. So let X bar be the biggest X coordinate in the left half, so that is

the sorted version of the points by X coordinate. Look at the N over two

smallest coordinate. So in this example where we have six points, all this means

is we draw, we imagine drawing a line. Between the third points, so that’s gonna

be X bar. The X coordinate of the third point from the left. Now since we’re

passed as input a copy of the points sorted by X coordinate we can figure out

what X bar is in constant time just by accessing the relevant entry of the array

PX. Now, the way we’re going to use this parameter Delta that we pass. So, remember

what Delta is. So, before we invoke the closest split pair of subroutine and the

recursive algorithm. We make our two recursive calls. We find the closest pair

on the left, the closest pair on the right, and Delta is whatever the smaller

of those two distances are. So, Delta is the parameter that controls whether or not

we actually care about the closest split pair or not. We care if and only if there

is a split pair at distance less than Delta. So, how do we use Delta? Well that

is going to determine the width of our strip. So, the strip is going to have

width to Delta and it’s going to be centered around X. And the first thing

we’re going to do is, we’re going to ignore forevermore, points which do not

lie in this vertical strip. So the rest of the algorithm will operate only on the

subset of P, the subset of the points that lie in this strip. And we’re gonna keep

track of them sorted by Y coordinate. So the formal way to say that they lie in

this strip is if they have X coordinate in the interval, with lower end point xbar

minus delta, and upper end point Xbar plus Delta. Now how long does it take to

construct this set SY sorted by Y coordinate? Well fortunately we’ve been

passed as input a sorted version of the points PY. So to extract SY from PY, all

we need to do is a simple linear scan through PY checking for each point where

it’s X coordinate is. So this can be done in linear time. Now I haven’t yet shown

you why it’s useful to have this sorted set as Y, but if you take it on faith that

it’s useful to have the points in this vertical strip sorted by Y coordinate, you

now see why it was useful that we did this merge sort all the way at the beginning of

the algorithm before we even underwent any recursion. Remember, what is our running

time goal for closest split pair? We want this to run in linear time. That means we

cannot sort. Inside the closest split [inaudible] subroutine. That would take

too long. We want this to be linear time. Fortunately, since we sorted once and for

all at the beginning of the closest pair algorithm, extracting sorted sub lists

from those sorted list of points can be done in linear time, which is within our

goals here. Now it’s the rest of the sub-routine where you’re never gonna

believe me that it does anything useful. So, I claim that, essentially, with a

linear scan through SY, we’re gonna be able to identify the closest split pair of

points in the interesting, unlucky case where there is such a split pair, with

distance less than Delta. So here’s what I mean by that linear scan through SY. So,

as we do the scan we’re gonna keep track of the closest pair of points of a

particular type that we’ve seen so far. So let me introduce some variables to keep

track of the best candidate we’ve seen so far. Is going to be a variable best which

will initialize to be delta remember we’re uninterested in split pairs unless they

have distance stripping less than delta. And then we’re going to keep track of the

points themselves. So we’ll initialize the best pair to be null. Now here’s the

linear scan. So we go through the points of SY in order of Y coordinate. Okay, well

not quite all the points of SY. We stop at the eighth to last point and you’ll see

why in a second. And then for each position I of the array SY we investigate

the seven subsequent points of this same array SY. So for J going from one to

seven, we look at the Ith and I+Jth entry of SY. So if SY looks something like this

array here, at any given point in this double four loop, we’re generally looking

at. An index I, a point in this, in these I [inaudible] of the array, and then some

really quite nearby point in the array, I+J, because J here is going to be at most

seven Okay, so we’re constantly looking at pairs in this array but we’re not looking

at all pairs of all. We’re only looking at pairs that are very close to each other,

within seven positions of each other. And what do we do for each choice of I and J?

Well, we just look at those points. We compute the distance. We see if it’s

better than all of the pairs of points of this form that we’ve looked at in the

past, and if it is better, then we remember it. So, we just remember the

best, i.e., closest pair of points of this particular type for choices of I and J of

this form. So in more detail, if the distance between the current pair of

points P and Q is better than the best we’ve seen so far, we reset the best pair

of points to be equal to P and Q and we reset the best distance, the closest

distancing so far, to be the distance between P and Q, and that’s it. Then, once

this double four loop terminates, we just return at the best fare. So, one possible

execution of closest split pair is that it never finds a pair of points, p and q with

distance left in delta. In that case this is going to return null and, then, in the

outer call, in the closest pair, obviously you interpret a null pair of points to

having infinite distance. So, if you call closest with pair and it doesn’t return

any points, then the interpretation is that there’s no interesting split pair of

points and you just return the better of the results of the two recursive calls p1,

q1 or p2, q2. Now as far as the running time of this subroutine. What happens

here. What we do constant work, just initializing the variables, then notice

that the number of points in s-y, well, in the worst case you have all of the points

of p so it’s going to be in those end points and. So you do a linear number of

iterations in the outer fore loop, but here’s the key point. In the inner fore

loop, right, normally double fore loops give rise to [inaudible] running time, but

in this inner fore loop, you only look at a constant number of other positions. We

only look at seven other positions. And for each of those seven positions, we only

do a constant number at work, right. We just compare distance and make a couple of

other comparisons and reset some variables. So for each of the linear

number of outer iterations, we do a constant amount of work, so that gives us

a running time of. O event for this part of the algorithm. So as I promised,

analyzing the running time of this closest split pair [inaudible] was not

challenging. We just in a straight forward way looked at all the operations. And

again, because in the key linear scan we only do constant work per index the

overall running time is big O of N just as we want it. So this does mean that our

overall recursive algorithm will have running time O of N log N. What is totally

not obvious and perhaps even unbelievable is that this subroutine satisfies the

correctness requirements that we wanted. And remember what we needed. We needed

that whenever we’re in the unlucky case whenever in fact the. Pair of points in

the whole point set is split. This sub-routine. Better find it. So, but it

does, and that’s made precise in the following correctness claim. So let me

phrase the claim in terms of an arbitrary split pair which has distance less than

delta, not necessarily the closest such pair. Suppose there exists. A P. On the

left, a point on the left side, and a point on the right side, so that it’s a

split pair. And suppose the distance of this pair is less than Q. Now there may or

may not be such a pair of points P.Q. Don’t forget what this parameter delta

means. What delta is by definition, is the minimum, of D. Of P. One Q. One, where

P.1Q.1 is closest pair of points that lie entirely in the left half of the point set

Q., and D. Of P.2, Q.2. Where similarly P2Q2 is the closest pair of points that

lies entirely on the right, inside of R, so. If there’s a split pair with distance

less than Delta, this is exactly the unlucky case of the algorithm. This is

exactly where neither recursive call successfully identifies the closest pair

of points. Instead, that closest pair is a split pair. On the other hand, if we are

in the lucky case, then there will not be any split pairs with distance less than

Delta. Because the closest pair lies either all on the left or all on the

right, and it’s not split. But remember, so we’re interested in the case where

there is a split pair, that has distance less than Delta. Where there is a split

pair that is the closest pair. So the claim has two parts. The first part, part

A, says the following, it says that there’s a split pair P and Q of this type

then P and Q are members of S, Y. Now, let me just sorta redraw the cartoon. So

remember what SY is. Sy is that vertical strip. And again, the way we got that, is,

we drew a line through a medium x coordinate, and then we fattened it by

Delta on either side. And then we focused only one points that lie in the vertical

strip. Now, notice our counts, split pair subroutine. If [inaudible] returns a pair

of points, it’s gonna return a pair of points PQ that belong to SY. First, if it

filters down to SY, then it does a linear search through SY. So if we wanna believe

that our subroutine identifies S split pairs of points, then, in particular, such

split pairs of points better show up in SY, they better survive the filtering

step. So that’s precisely what part A of the claim is. Here’s part B of the claim.

And this is the more remarkable part of the plan, which is that P and Q are almost

next to each other in this sorted array SY. So they’re not necessarily adjacent

but they’re very close. They’re within seven positions away from each other. So

this is really the remarkable part of the algorithm. This is really what’s

surprising and what makes the whole algorithm work. So, just to make sure that

we’re all clear on everything, let’s show that if we prove this claim, then we’re

done. Then we have a correct fast implementation of a closest pair

algorithm. I certainly owe you the proof of the claim. That’s what the next video’s

gonna be all about. But let’s show that if the claim is true, then we’re home free.

So if this claim is true, then so is the following corollary, which I’ll call

corollary one. So corollary one says, if we’re in the unlucky case that we

discussed earlier. If we’re in the case where the closest point in the whole point

set P does not lie both on the left, does not lie both on the right. But rather, has

one point on the left and one on the right. That is, it’s a split pair. Then in

fact, the counts pair subroutine will correctly identify the closest split pair

and therefore the closest pair overall. Why is this true? Well what does count

split pair do? “Kay, so it has the double four through. And it, it thereby

explicitly examines a bunch of pairs of points, and it remembers the closest pair

of all the pairs of points that it examines. What does this, so what are the

criteria that are necessary for [inaudible] a pair to examine a pair of

points? Well, first of all the. Points p and q both have to survive the filtering

step. And make it into the [inaudible] as y. Right so cancel the pair. Only searches

over the ray as y. Secondly, it only searches over rays of point almost

adjacent to x y. That are only seven positions [inaudible]. But amongst the

pairs of points that satisfy those two criteria, counts, but [inaudible]

certainly compute the closest such pair, right? It just explicitly remembers the

best of them. Now, what’s the content of the claim? Well, the claim is guaranteeing

that every potentially interesting split pair of points, namely, every split pair

of points with distance less than Delta, meets. Both of the criteria which are

necessary to be examined by the count-split pair sub routine. So first of

all, and this is the content of part a, if you have an interesting split pair of

points with distance less than delta, then they’ll both survive the filtering step.

They’ll both make it into the array as Y. Part A says that. Part B says they’re

almost adjacent in SY. So you have an interesting split pair of points meaning

it has distance less than delta, then they will in fact be at most seven positions

apart. Therefore count-split pair will examine all such split pairs, all split

pairs with distances less than delta and, just by construction, it will compute the

closest pair of all of them. So again, in the unlucky case where the best pair of

points is a split pair, then this claim guarantees that the count-split pair will

compute the closest pair of points. Therefore, having handled correctness, we

can just combine that with our earlier observations about running time. And

corollary two just says, if he can prove the claim, then we have everything we

wanted. We have a correct O of N login, implementation for the closest pair of

points. So with further work and lot more ingenuity, we’ve replicated the guarantee

that we got, just by sorting for the one dimensional case. Now again this

corollaries hold only if the plane is in fact true. And I have given you no

justification of this plane. Even the statement of the plane, might be a little

bit shocking. For you, I would demand an explanation. For why this one is true and

that’s what I’m gonna give you in the next