Tip:
Highlight text to annotate it
X
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