Video 2-13: Online Greedy Arborally Satisfied Superset

0:04 Okay. Uh, we've already formulated the problem yesterday of what we want to do with these points. Find the smallest arborally satisfied supererset. Um, keep that in mind. And you can then uh interpret an algorithm that does this as either an offline algorithm or an online algorithm. The offline part is what we've done in the proof. we've looked into the future and built the tree based on that. That's offline by definition. If you uh instead reveal the next slice of the input, which is really just one access dot, right? Uh but you can say there's this time slice of x. In general, you could potentially define this problem to have more than one access at a time. The points don't really care. All the examples that we've done um had a single red dot in each row. That's not uh a problem to um generalize from that. But if we stick with that, this XT is really just one dot. And then an online algorithm can take uh its current view of the world without knowing the future axises, but decide to place some dots to make this satisfied.

1:19 And of course, you can't revisit once you're further down in the picture. You can't change your mind in the past and say, "Ah, I'm actually changing this around." That it also doesn't work in an online algorithm.

1:32 Okay, so we found um a new new representation. And that turns out to be if you go row by row down the picture, there's a very natural choice for for putting the dots, which is the greedy ass algorithm. And there's a there's a certain tradition in this in this field of dynamic optimality to have say uh not quite grown-up abbreviations for various things. That's one of those uh but it's memorable. So what you do is you um at each point at each time step when you add this new point you satisfy all the rectangles that you have to and nothing else. So all the new unsatisfied rectangles you satisfy now and then you move on. Uh let's do a small example just to illustrate that a bit again. Let's do the pin wheel again.

2:32 Or let Yeah, let's do this one first. Um, so these are the axises. Now, uh, you have to imagine this is a sweep line algorithm. I'm starting at the top. I can't see what what's below. I can only see what's above me and my current point. So, if I arrive at this line, uh, let me let me try something innovative. Uh, the Okay, fun.

3:21 Maybe not dotted. Uh, imagine that this is um completely intransparent. So, you can't see what's behind the box, obvious wants to keep dotted on. Now we get revealed the next point and we see oh there is a rectangle that I need to satisfy namely these two dots. Uh I need to put a dot somewhere. Now I can't put it anywhere up here that's changing the past. I can only put it here on this line. I could put it here but that's kind of stupid right? I would create another open rectangle with these two. If I put it here I have another one. So the only sensible choice is put it in this corner. And that's a rule. Whenever you find a an independent an unsatisfied rectangle, jumping ahead of myself, uh find the smallest one and put the dot in the corner. Uh that's visually what's happening. So that's that's all in this case. No more unsatisfied rectangles. I'm revealing the next point. What happens? There's a bunch of rectangles. Um, so there's this one, there's this one, and there's this one.

4:52 Uh, the smallest among those is is clearly this one. So if I put a dot here, it happens to satisfy all the other rectangles.

5:04 Now, also notice what happens if you um interpret this as a tree. Uh again this is the offline view that knows the future but we we kind of apart from this note okay let's let's let's just say up to this point what would the tree have looked like in here three is accessed first so that becomes the root and then I have four on one side in here one is touched first and then two so this should be the shape of the tree before I'm doing anything then I'm touching only the root lucky A and no no things I can change. Then I'm touching three and one. Well, that's the path from the root to one. Now I could rearrange uh but indeed among three and one we see that three is touched again sooner and so the tree stays.

5:59 Okay. Uh I'm revealing the last dot. Maybe get rid of this. And that opens a few more rectangles that we have to satisfy. There's this, there's this, there's this, there's this, there's this a bunch of kind of with with everything almost by definition, you have a rectangle apart from this um points in your own in your own column. But then again, if you take the smallest only, this one is unsatisfied. Now there's a new rectangle. Whenever I add a dot, there's new rectangles formed. I didn't check this carefully in the previous step I think uh but there happens to be only this triangle created this rectangle created that had already a dot uh at this time there's another rectangle namely this one that isn't satisfied so I have to put another dot but these are all all happy so if you do this a few times you get rather uh quick and skilled with this for some reason um it's rather fun and not not at all complicated to to execute. Whereas thinking about the trees that happen in the at the same time is is much more much more taxing somehow. Okay, maybe it's uh just getting used to it.

7:22 So uh that's a greedy algorithm for building an arborally satisfied point set. Um it is greedy in the point set and it is an online algorithm in the point set. Uh it would be cool if that was also a greedy algorithm with respect to the binary search trees. But that isn't quite clear yet because again here I've built this this initial tree by looking at what happens in the future. I can put the points offline uh online excuse me. I can I can assign the points line by line in a sweep line only looking at the past and the present. But whether the tree can be made following that without looking into the future is not so clear. Um and indeed this uh I I'll come back to that in a second. There's one more um one more point I wanted to make. uh just on the point set you can ask how good is this algorithm and it seems to work surprisingly well.

8:28 Uh there's a simple example that shows that it's not optimal. Uh and that's essentially this this little example um with just three keys and you can make it as long as you want in terms of time. you uh you start with the middle one and then you alternate between left and right.

9:05 So if you see this think about this uh from the tree perspective in this case again you're touching key2 once and then never again what kind of tree would you want to build?

9:26 what's the cost for these subsequent axises? Always two. I'm always touching this or this side. Uh how about um okay, let's see. Um if you follow the algorithm for the greedy point set, that is precisely what happens. You put a dot here to satisfy that rectangle. Then you come here. Ah, smallest rectangle is this. And now everyone's happy. So indeed, greedy ass puts a dot along this middle column. And that means precisely this tree. Now I claim this is not optimal because you can do a different point set. And here I think it's it's kind of cool that uh in the points it's very obvious that this is way better.

10:16 Uh, okay. I can't really get rid of the points without deleting more. >> Yeah, kind of not. But I wanted the picture to be nice and clean. Um what you could also do is in the first axis be uh clever and touch everything and then say always just do this and you observe here all the rectangles are satisfied. Oopsie via the top.

10:56 The only new points that potentially give me new unsatisfied rectangles are always these guys. But then I put the dot in the first column. So what kind of tree is this? Well, it it always touches the one. So the one is in the root. Initially, I don't know exactly, right? Initially, it's this weird ambiguous maximally ambiguous tree where everything is in the root. But then if you look down um it gets broken into uh the one at the root and then here the three and the two down there. And then the tree never changes. But lo and behold, every other axis costs just one and the others cost two. So this is 1.5 on average and this is two on average. So it's a three half uh difference. There's a factor of three half between those two. Of course, this is not an offline algorithm. It kind of uses crucially that I I invest at the beginning to touch the entire tree and rearrange it.

12:05 And of course, you can try to pump up this example. Um, but this is actually fairly hard to come up with bad cases for this algorithm. Most of the time this greedy sweep line seems to work very well and to use a a quantitative term.

12:24 The reason why I'm touching this is because again this is a open problem. Um but there's more. It turns out that you can translate this this greedy algorithm that is online for the point set also into a proper greedy algorithm for the trees. Uh what you need to do is essentially just resolve this ambiguity and you can do it lazily whenever there's a case where previously in my example I said ah no bad luck we have to look into the future to decide what the tree looks like. Uh that was a bit of a a smoke mirror. Um because you don't really have to you can leave the tree in some ambiguous state with a clever data structure. And so this this needs um conceptually it's easy. You just leave the treat nodes that are not disambiguated yet conceptually at the same level. And until you touch them again, you don't care what they look like. But when you touch them again, you've broken the tie.

13:32 So in a way, you can always lazily do that. But doing this within this confined with this this constrained model of binary search trees with, you know, only a pointer that can move in five directions and so on uh or do five things in each time step. Uh that's a bit painful. So I'm I'm going to spare you any of the details. um the the original paper that I cited initially uh gives some more some more details on this. I hope conceptually it's not so hard to imagine that essentially this tree looking at what is tight at the moment and delaying it till later is uh is possible. The really crazy thing is that this is indeed the same as this greedy future algorithm that we've looked at before. The greedy future algorithm was an offline algorithm because it said uh at each time at each time step I'm following the search path to the element I have to access now and then I'm rearranging the element on the the top tree the top part of the tree that I'm touching so that the next axis breaks ties. In other words, I'm building a tree based on next axises.

14:43 even used the same phrasing at the time. So maybe the connection isn't so surprising. Uh I found this shocking when I learned about it because this algorithm is very natural but it's so much offline that it doesn't even come to uh to your mind that you can somehow implement this. But via this this indirect way to view it as points and having uh the right I guess the the trip idea you could have had otherwise but this is how it historically uh was discovered. You can indeed make this this offline algorithm into an online algorithm properly working on BSTs. is not quite as clean and easy to describe as SPL with its two or three rules uh for rotations and that's all because these these split trees somehow need to give you uh to break these these ties among a whole bunch of nodes in constant time and to do that in the in the search tree model is a bit more painful. So the algorithm is a little less clean and practical.

15:45 Uh, but at least it exists. Um, conceptually easy to describe. Yeah. Where did I jump to? Nope. That was not what I wanted. So indeed you can implement this as an online algorithm and this is the second algorithm that I mentioned before. Indeed by now we know more about this algorithm than about slay in terms of coming close to being constant competitive. So if you want if you want to bet on current knowledge, this is even more likely than splay to be the answer for this open question. Uh a few more things known maybe because it's a bit cleaner and in this point pointbased geometric view is more natural to argue about. Um on the the downside is that it's probably a theoretical result only because u much less clear how to implement this um in practice. So that the time to do the next step is is as fast as with