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
