0:03

Okay next we're gonna look at another extension of geometric algorithms to

Â process slightly more complicated objects and then we'll see an important

Â application. This is called interval search. So now instead of points, our data

Â is intervals. So this is, we'll start with one dimension as before and right away you

Â can see that it's a more complicated problem than we've been dealing with. So

Â we want to support the following operations. We wanna be able to insert an

Â interval. So an interval is just a left endpoint, right endpoint of a

Â 1-dimensional data or points on the line. We wanna be able to Insert an interval

Â search for an interval, delete an interval but the main thing is we want the interval

Â intersection query. So given a query interval, we want to find all intervals in

Â the data structure that overlap that interval or find any interval we'll start

Â with that simpler problem. So how are we going to support that? So this is the API

Â in Java code [cough], so We, have, intervals, so instead of one key we have

Â two, which is left and right end points of the interval for input. And [inaudible],

Â and then we have delete, and then we have intersects. And again simplify the code,

Â we are going to make the non degeneracy assumption that no two intervals have the

Â same left end point. [cough] and, [cough]. Easy, easy to fix but, but we don't

Â simplify the code. So now we'll look at a data structure called an interval search

Â tree that helps to solve this problem. And, it's a extremely, simple algorithim,

Â but surprisingly, complicated to understand, so we'll go slowly. So the

Â first thing is what we're going to do is use the left end point of each interval as

Â the binary search tree key. So our, eh, our node stored intervals, but we only use

Â our left end point as the key. So this is the binary search tree that's built from

Â those five intervals, six intervals in our example. Seventeen, nineteen is at the

Â root, so everybody with a le ft end point less than seventeen is to the left, the

Â left end point greater than seventeen is to the right and so forth. So that's a

Â binary search tree built, from those intervals. So that's easy. I just build a

Â binary search tree. I just use, the left end point, as the search key. But we're

Â also in the, each node of the tree, we're gonna store, not just the interval. But

Â we're gonna store the, largest endpoint in the subtree rooted at that node. So at

Â every node, we're gonna store the maximum endpoint and subtree rooted at that node.

Â So at the root, the maximum endpoint or the rightmost point covered by an

Â interval, is 24. So we [inaudible] 24 at the root, and, of course, the right

Â subtree. And the left subtree. The max end point is that eighteen so that's what we

Â store for the associated data with the note to the left of the root and so forth.

Â So. We going to have to, that's data that we're going to have to maintain when we do

Â an insert and it's data that we'll use when we're doing an interval-intersection

Â search. So let's take a look at an insertion into an interval search tree

Â with a demo. All right, so, the, insertion algorithm is pretty simple. We do the BST

Â insertion, just so we have to do that, update of the maximum in each node on the

Â search path. So, to insert 16/22 in this tree, while we use the, left endpoint as

Â the search key, sixteen is the left endpoint of our insert interval [cough].

Â We compare that with seventeen and therefore go left. How sixteen is bigger

Â than five so we go right. Now sixteen is bigger than fifteen so we go right. And

Â that's null, so that's where we insert our new, interval. [sound]. So now, we're

Â gonna go back up the tree. And, for every node that we encounter, it could be that,

Â our right endpoint of our interval, is bigger than what was there. So we have to

Â check, all the way up the path, the maximum in each node on the path. So we

Â have to check each node, to see if 22 is bigger, and, for the three nodes to the

Â left it is bigger than eighteen. For the node at the root, it's not. That stays to

Â be 24. So, it's just binary tree insertion, but then after the insertion on

Â the way up, we go ahead and, check, if the maximum that we have is bigger than the

Â maximum there and update it if necessary. So easy to code. [sound]. Alright, so now

Â about, how do we do a, a search. So the searches is definitely more complicated

Â and kind of mysterious, but let's look at the rules for search in an interval search

Â tree. Alright so now we're gonna look to see if we have an intersection what a. We

Â want to find just. Any interval that intersects this query interval 23 25.

Â We're not gonna try to find them all we'll get back to that in a minute. Try to find

Â any interval that intersects our query interval. So let's, let's see what we have

Â to do. So first thing is if At the root, we have an intersection, then we're done.

Â We just return. In this case, 2325 does not intersect, 1719. So, we have to go

Â down the tree somewhere. So left subtree is [inaudible] right, okay? Otherwise, we

Â have to check whether the max endpoint in the left subtree is less than, the low

Â point in our interval. [inaudible] it's easy to see, well, if that's the case,

Â then we're not gonna find an intersection. In the left. The maximum end-point in the

Â left is 22, and we're looking for 23, and we're not gonna find anything there, so we

Â just wanna go right. So in this case we'll go right 22, 23 no inter sectional left,

Â so we go right and now we do find an intersection 21, 24 does intersect with

Â 23, 25 because 23 is in the middle there, so we find an intersection. Now on the

Â other hand, let's say they were looking for 1214, so no intersection. So. All the

Â algorithm says is that, if you didn't go right, go left. So let's go left, in this

Â case. So we weren't able to show that there was no intersection, on the left.

Â So, so we're gonna go left. In this we compare twelve fourteen to five eight, so

Â now we apply the same rules. Does it intersect? No, it doesn't intersect. So

Â should we go left. Well no, the maximum, end point in the left node is eight. So we

Â can have intersection there, so we gonna go right, [inaudible] to twelve and go

Â right. So, now does twelve, fourteen intersect fifteen, eighteen it does not so

Â there's no intersection so now what do we do. Should we go left no the max in point

Â on left is ten so we shouldn't go left. So we're going to go right. Those 12-14

Â intersect 16-22. It does not, So, now, the left end point's null. And so we're just

Â gonna go right. And there's no intersection. So in both cases we just

Â went along one path in the tree to determine whether or not there was an

Â interval or intersection. Let's look at one more example. 21, 23. So let's see. 21

Â thru 23 to seventeen, nineteen. They do not intersect, so now, what are we gonna

Â do next? Well we're gonna compare the left sub-tree, and it's Not, 22 falls within

Â our interval so it's not less than'r' so there might be an intersection there so we

Â better go to the left, so we do go to the left. Now we compare against 5-8, and

Â there's no intersection. So now, we're gonna go left to right. Well, we're gonna

Â go to the right, because, the max endpoint in the left subtree is eight, and our

Â interval's 21, so no intersection on the left. So we're gonna go right.

Â Intersection 21231518. They do not intersect. So now, do we go left or right?

Â Again ten is less than our left endpoint 21. So we better go to the right. [cough].

Â And now 2123 does intersect 1622, so we return and intersection. Again one path

Â through the tree to determine an intersection. So from these rules you can

Â see that the man of code required to implement this intersecting inter role is

Â extremely low. Just check for an intersection, if we find it ret urn if

Â left is no we go right. Otherwise if the max is less than low we go right.

Â Otherwise we go left. Could hardly be simpler. Really amazingly simple and

Â efficient algorithm. We should convince ourselves really that it always works and

Â so we'll spend just a moment on a short proof. So let's look at the, the cases

Â that could happen. So first thing is if the search goes right. Then there's no

Â intersection on the left. And that's easy to convince ourselves of that just from,

Â from what we did in the demo. Of course, if the last sub-tree's empty, there's no

Â intersection there. But if the max endpoint in the left sub-tree is less than

Â low, that means every interval in the left sub-tree has a max endpoint less than mah,

Â low, and so therefore it can't intersect. So if you go right, there's no

Â intersection in the left. Any possible intersection would have to be in the

Â right, And then the other point is that if you go left, then either there's an

Â intersection there, or there's no intersections at all. So Lets suppose that

Â there is no intersect, and that's equivalent to saying, if there is no

Â intersection in the left then there is no intersection in the right. So lets look at

Â it if there is no intersection in the left, since we went to the left and then

Â we have got, low less than max. But, for any interval, in the right subtree, its

Â got to appear after. Low. Be, because since there's no intersections in the left

Â sub tree high has gotta be less than C. Where, because they're sorted by left N

Â point. And then that means that C-s got to be less than A if it is in the right, so

Â therefore there can't be any interesection in the right either. No intersection in

Â the left means no intersections at all, so those two cases is enough to show that

Â this algebroid finds an intersection, if there is one. And the other thing we can

Â do with this is just use a red-black BST to guarantee that we solved this in time

Â proportional to log in. So insert, find, delete, and find any interval that

Â intersects. All take time, guaranteed, proportional to log in. And if we wanna

Â find all intervals we just have to run the algorithm fur Each interval that's, until

Â we come up against no intersection, so it'll take time proportional to R log N if

Â there's R intervals that intersect. The theoretical best that you could possibly

Â do would be R plus log N but in practice R log N is quite efficient. This is an easy

Â and very efficient algorithm to solve this interval search problem and as we'll see

Â this algorithm. It's applicable to an important application that we'll see in a

Â