Video 2-14: Independent Rectangle Lower Bound

0:04 There's one more thing we can squeeze out of this geometric view. And does it that is lower bounds for the optimal solution specific to a given instance. And again, I think this is this is kind of natural. If you're given a point set, it ought to be easier to work out how many points you have to add for this specific point set than the original question of here's an access sequence among all the possible ways of rearranging BSTs after each step, what's the best uh choice and can you find a lower bound for that? So, here all we need to do is somehow bound how many points do you always have to add to satisfy all rectangles in your input including the ones you create by adding points. That's the tricky bit. But, you'll see we'll mostly ignore that part. Uh the crucial thing is um this notion of independent rectangles.

0:59 Um let me let me draw instead of writing formally what different cases are. Conceptually, an independent rectangle is just uh an unsatisfied rectangle. And independent only makes sense if you talk about several of them. So, a set of rectangles is is independent if uh no corner is strictly within the other. So, um the dependent cases the ones that we don't like are say cases like this.

1:48 Right, this is defined by these two point these points. This uh we don't like. Uh but, also if the corner is just defined um where the points here no no point lies within the other rectangle, but still we define these as dependent because the the empty corners count as corners. Uh on the other side, um what counts as independent rectangles is of course anything that's just completely disjoint or also some more subtle configurations if they overlap, but they don't overlap in any of the corners.

2:34 Um or this is the weird one why it says in the inside they can share a corner point. And that is also fine. This counts as independent because no corner is strictly in the inside of any of the other rectangles.

2:58 Now, intuitively you should think whenever you have such independent rectangles, you have to satisfy them all if Y is any arbitrarily satisfied superset. So, the the largest number of independent rectangles you can find should be a an upper bound a lower bound for the number of points you have to add.

3:28 Um it's a tiny bit more subtle um because you lose a factor 1/2 uh because of the interaction that sometimes one point can satisfy several rectangles still. And indeed, if you just look at the cases, uh and clearly here if I put a dot here both of these are happy and this could be an arbitrarily an arbitrary number of rectangles that somehow share this. These are even worse, right? If I if I somehow choose to add this one, I might satisfy unbounded number of rectangles in one go. So, it's not completely trivial to get to a lower bound, but still you can do at the loss of a of a factor 1/2, you can show a lower bound. And again, I want to stress before we dive into the proof a bit, I want to stress how clean the statement is. Even though this factor 1/2 is is annoying, but it's necessary. All you need to do is find sets of independent rectangles, and then you get a lower bound for your specific input.

4:34 And the that X occurs here is just because we can't delete points. So, any any superset has to be a superset, tada. But you have to essentially say one point is added for every other independent rectangle that you find. So, the more independent rectangles you find, the stronger your lower bound.

5:05 Uh the proof is very insightful because it gives another construction, so I want to I want to do it in detail. And also, it shows why this factor 1/2 pops up. Uh the trick is to separately consider two types of rectangles.

5:27 To avoid having these annoying interactions where a single point might satisfy many of them, and then you have no control over how this behaves. And the two type of rectangles are simply about the slope of or which which points define the rectangle.

5:43 And we call this the the plus rectangles because they have a positive slope in the defining points and this is the negative rectangles. And I will will focus on just one type of these and show that for with this uh if you just look at the independent rectangles of this positive type then you can bound the points and with the same symmetric argument works for the other ones and then uh the independent rectangles are all of one of these two types. So, the larger of the subset that's only positive or only negative will have to have at least half the size of the overall set. And that's where we get the bound from.

6:40 So, define this plus satisfied if all of these are satisfied. are really satisfied and we just ignore the others as if they weren't there.

7:13 Uh then we can also define what is the optimum if you just focus on these upward slope ones. That's the smallest superset Y that's satisfied with this new notion.

7:33 Uh messed up. a lemma just for these um positive rectangles. We'll show that this opt plus that's at least the set of the original X plus the largest set of independent rectangles, but now I'm I'm only constraining it to the positive rectangles.

8:17 So, uh this is supposed to mean, right? I set of independent rectangles. Otherwise, independence is defined the same way, but uh of course, you can exclude some cases um because we only look at these these positive rectangles.

8:53 Okay? Uh the first step in proving this lemma is to show that uh we can essentially charge rectangles to certain points that uh that can satisfy this rectangle, but that cannot be charged too often, >> [snorts] >> which means um we need to pay a certain number of points for each of these rectangles. And so, uh every every solution that satisfies all these independent rectangles has to have at least that many points. So, how do we do that? Uh We find some rectangle from this set of independent rectangles.

9:48 >> [snorts] >> And the way to choose it is to choose one that has maximal vertical horizontal extension. But ah, okay, let me draw this a bit bigger.

10:20 And there's nothing that's wider than it. Now, what can other rectangles look like that are also in this set of independent rectangles? They can lie completely elsewhere. They might be to the left of it or to the right of it. These are all kind of boring. Uh, the only other case that we can have is rectangles that somehow span this.

10:47 But they cannot overlap the points. Otherwise, they wouldn't be independent. >> [snorts] >> Uh, the other fun case we can have is this shared corners. This can happen. And of course, can also uh, happen on this side. So, I could have some And that's inside. That's not possible, but here it could be.

11:13 And I could have many of these crossing ones. This unclear. But, note that these are all in a way uh, arranged left to right, and they can't overlap or not arbitrarily overlap. I cannot have another rectangle looking like this because I've chose chosen the widest one. So, this can't happen. I can't have anything that crosses through these, but stops in the middle, because then they are not independent. So, the the whole point about this construction is there will be a line, a vertical line, somewhere inside this widest rectangle that is not intersected by any other rectangle. This line is unique and belongs only to this to this fat rectangle here.

12:09 That is my R, the widest of them all. Among those I'm still looking at. So, we can always find this line by the way these are arranged, and the second step is we we find two specific points. Uh because R is is an unsatisfied rectangle, I have to have some points that satisfy it. And there could be many, we don't know in general what opt does, right? Uh but we'll show that there's two specific points that are essentially looking like this.

13:05 And uh because these are close to this red line, and they're the line is unique, these two green dots, they satisfy R, and they don't satisfy anything else. So, um we'll charge this independent rectangle to these points.

13:55 >> And what I mean by charge part to these is that for every independent rectangle will eventually have to show that we have to add a point. And that's the way uh we'll we'll establish this correspondence between op has to pay a point for each of these Rs then uh this this lemma statement follows. Um what I have to show is how to choose these points. Now, I'm I think we actually use an assumption here that maybe should should go here.

14:28 In In the original axis in the axis sequence we assume that all the X and Y coordinates are distinct. For the geometers, this means the points that is in in uh general position. This is fine in Y direction. Inter- In the time dimension, this was always the case. In the key dimension, it's a bit questionable from the get-go. Now, there's two answers to this. Uh one answer is the BST problem is already interesting on permutations where you touch every node only once, and you could say let's uh focus on this part. Uh the other idea is you can if you had um uh an input where you touch the same key several times, if you split that key into several keys that are very close, wiggle them around by an epsilon, it doesn't change much what the binary search tree can do. Uh, remember these kind of finger bounds that we had for splay trees that may also hint in this direction.

15:44 Uh, here it it's a technical assumption that just makes the proof much much cleaner. Uh, so this is something we'll have to uh, buy at this point. Um, and it could be that the paper makes may gets rid of this assumption in some clever way in the general sense without waving waving hands.

16:14 Okay, so we have the um widest rectangle. I also insist that this red line is the leftmost place I can find this this uh red line.

16:30 Um, maybe that's not even crucial. So, how to choose these points though? Um, I'm going to choose P Um, so in inside inside R, but it's chosen from opt.

17:17 That is left of the red line. And I guess uh it could be that P is the corner point of this rectangle if there's no other point. That's one valid option. Uh but if there's a way to move closer to the red line, we do that. And among all those that are rightmost, I pick the highest. Um This is this thing here. It's the topmost rightmost point.

18:01 Uh so what this means um Let me just draw P uh and R without the other rectangles interfering. So we go as close uh as we can to the right.

18:22 And then as high as we can up. So here's a point. But then nothing above this. So I don't know um let's draw empty as white. And also um So this this is all empty. There's no more points in here. Uh whereas the other part here, I don't know. There could be more points in here or not. Arbitrary. That's the point on the left. Now we choose Q somewhat uh similar. It's the bottommost point to the um the bottom-most and left-most inside the rectangle and in our optimal solution Uh and that is at least as that's uh let's say north of P. So, it can't be below P. It's chosen to be above P.

19:55 And again um there's nothing further left of Q. This has to be empty. And there's nothing below Q here. I don't know if you can see the white at all. Uh There could be more points in in this part, which we don't care about. Now, observe that actually P and Q must be uh Because they otherwise would form an unsatisfied rectangle. And this is opt. They're chosen from opt. They can't have this unsatisfied rectangle here. There are no other points by the way we chose them. All right, P was the top-most. There is no no thing no point here. And there's nothing to the right of P up to the red line because it was the last of all those, the right-most ones. And similarly, Q, there's nothing to the left. Uh and there's nothing to the bottom. So, there's no other point. So, this can't happen. They cannot be on the same vertical line because they're to the left and to the right of the red line. So, they have to be on the same horizontal line as as we've drawn it here.

21:32 Yep. Where's my pen? So, as I said, we'll charge this largest widest rectangle R to this uh pair PQ. Um but that's not good enough. It could happen that several rectangles charge the same points, then it would be uh no use. Um but indeed, this pair of points cannot be charged again.

22:20 I should maybe say uh after this, we essentially get uh remove R from consideration and look at the next widest rectangle, find a new red line, find new Ps and Qs.

22:50 And all we have to worry about is potentially charging the same points twice. Uh but this can't happen because this this red line was unique. There's no other rectangle that contains the the line. And so, uh there's no other rectangle that contains both P and Q.

23:11 So, the pair can't be charged again. Um And the final thing that's missing is this is the I think the only place where we make use of the assumption, which means it might be able to lift it. So, uh because P and Q are on the same Y line, on uh Let's use the same phrasing as above. They can't both be part of the original input by assumption.

23:53 Uh We can't have that P and Q is a subset of X of the original access sequence. Now, if this was only you needed in this direction, that'd be fine even for general access sequences, right?

24:08 Um it could be that for the symmetric case of the downward slope rectangles, uh you can flip the whole argument. I was I was worried if maybe there you need a horizontal red line. Then you would need this argument for the same X line. But why would you need that? You could just take um the same construction seems to work if you flip topmost and bottommost, but still keep the line vertical. So, maybe uh it's enough that all the Y coordinates are distinct, and that is an assumption we are very happy with. This is the only place I think we use this. Uh that here because they're uh not because they're on the same timeline, only one can be an original access, hence the other has to be added by um opt, and so contributes to one of these above the input. That's that's all. For every rectangle in this set of independent positive rectangles, we find one point that was not in the original input, but that needs to be part of the optimal solution.

25:31 And that's for the lemma. Technically, we're not done. Uh so similarly, and I hope the symmetry doesn't flip vertical and and horizontal lines. Um we get the result for these downward slopes um independent rectangles.

26:07 And any set of independent rectangles I is a disjoint union of those that are upward sloped, those that are downward sloped. So, uh the maximum of the two And that's it, right? That follows uh that that proves the lower bound from above a while ago, so here it is. Uh which means you can now, given some point set, you can relatively easily find an upper bound using the greedy algorithm, greedy S. And you can also find a corresponding lower bound. And um if they are close, you know a very good solution. Have a a certificate that the greedy algorithm, even though we don't know any upper bounds on its um quality really yet, I can't be too bad.

27:27 So, the only downside is finding this largest set of independent rectangles is in itself a hard problem. Um is a sort of set cover thing. I mean, you're trying to find something that's like an independent set in a graph of some sort, right? So, it's maybe not so surprising that this isn't so easy. But, here's another cool thing by the same virtue or same trick, you can find um you can do the greedy algorithm sweep line down and uh only satisfy the positive new rectangles that you formed by adding the next point. And that gives you some set of dot of points that are positive satisfied in the sense we defined. So, all the positive rectangles are satisfied. And you can do the same thing with the negative rectangles. That gives you a point set that satisfies all the negative ones. And um uh you can take the better of the two because what we've really shown, I mean, this is the statement that I presented as the theorem, but what we've actually shown is is the lemma for the two versions.

28:38 So, if you find a lower bound for the largest set of positive independent rectangles or negative independent rectangles, that's just as good as the original theorem. So, you just use the higher of the two lower bounds, and that's that's your simple to compute lower bound. It may not be tight, or it may not be the best independent rectangle bound that there is, but at least it's one you can compute in a sweep line, same as the upper bound. There's somehow somehow funny how this connects that the same sweep line algorithm, if you look at all rectangles, gives you an upper bound. If you only look at one type of rectangle, gives you a lower bound. Without changing any other thing in the algorithm.

29:31 So, I don't know if this is clear enough. So, same sweep line as greedy as I was too enthusiastic today to take a break. I'm sorry, I forgot.

29:59 Yeah, maybe. That's what you said. I think it's not completely obvious why this greedy algorithm gives a lower bound on the set of independent rectangles. I think this may need an argument. Um I think the point is just that the interference between rectangles of the same same sign is is much easier. If you have one that's created Okay, let's let's go off script for this one and see if we can easily make an argument here. There's this new point and there may be I guess the sweep line is on this point and there's various points from before.

31:16 As I am only looking at the say is the downward slope because that's how I drew it. There would be an unsatisfied rectangle for this. And I would satisfy there's one for this. So, I would add a point for this one. And then I don't have to look to the right at all. And for all these that I formed here's the crucial thing. I think when I add a new point, all the rectangles I directly generate are all of this type that they share the corner and so they're independent.

31:49 Now, of course, it could happen that there um that there's another um another point where these newly added points add rectangles with. Or maybe that doesn't even ever happen. Um So, that there could be another point here.

32:15 And from here to here, that's already satisfied because there's something in between. But now this this red point here escalates further, right? There I need to add No, no, forget it. This one's inside. Uh What if this black is below the other one? Then I need another another new point here, right? But you could have argued it's also shared with this one.

32:48 So I could either say this is my rectangle that I need to satisfy or I could say it's the bigger one. It's it's already satisfied by these points, but it's normally counting them as the same. So what I'm what I'm trying to argue is all the points that you add in a sweep line step come from an independent rectangle formed with exactly this new dot. Which means they all have this shape of being sharing a corner. Because that's the only point that's new uh apart from these others that are later added. If that's the case, then clearly every point we add corresponds to an independent rectangle in the input. That would trivially prove that the the signed greedy, so finding greedily only say the negative slope rectangles and satisfying them gives you a set of independent rectangles. Not just a point set that satisfies those, but the number of points is the same as a number of independent rectangles.

33:58 all the magic comes from restricting the slopes, making this configuration uh very simple. Where uh if you also had to look to the right for the upward slope rectangles, they can interact in funny ways.

34:14 Let's take this as uh an intuition and not a formal proof. Um I'm not a I I wouldn't be 100% convinced if that's all the cases that can happen without double-checking.

34:29 Either way, um this is proven, that's for sure, um that if you do just the signed version of the greedy, you get a lower bound for these independent rectangles. So, you can use this as a lower bound. Um, you can even prove that what you get from this signed greedy is a constant factor approximation, but it's not really what we would want, a constant factor approximation for the optimal lower bound or for I mean, there's only one opt. It's the optimal solution, which is lower and upper bound at the same time. Uh, we only get a a constant factor approximation for the best independent rectangle bound. So, the signed greedy finds a set of independent rectangles that's a constant factor, I think factor four away from the largest set of independent rectangles without restricting the signs. What's unclear is whether the independent rectangle bound gives you something that's within a constant factor of opt. I think it's rather, um, I think it's unlike, it may be known that it's not the case.

35:36 So, there there are cases where opt and this bound are further apart. Don't quote me on this. Um, I feel if this was known uh, there was a a somewhat better statement about this. Okay. I think that's all uh, all I wanted to say about this dynamic optimality problem. Uh, I wish I had some that this before about the greedy future. Let me remind you.

36:18 Uh, there's this this open problem at the time I only stated it for greedy future, which we now know is an actual online algorithm. Um, there's only this problem formulated whether greedy is an approximation to opt. Now that we know that it's an online algorithm, this approximation factor is actually a competitive ratio. If you think about it, it's the same it's the same concept. It's just that we call it differently because we compare different things. But now that we know that the quality that the greedy future algorithm achieves is not just an offline approximation to the optimal, but uh can be done online. Uh the same question is is is greedy as constant competitive? And we don't know. We don't even know this. We don't even know if it's less than the trivial competitive ratio.

37:06 Uh similar as for splay trees, this is kind of properties that I uh presented from the access lemma, all these uh working set bound and static finger and static optimality and what was the fourth? Uh the fourth, you can look it up. Um these these also hold for the greedy as algorithm or for for um uh greedy future.

37:39 And some more refined ones. Um Let me add this uh informally as an open problem. I'm going to stick with the with the name.

38:27 >> Yeah, and both is both is still open. Uh I quoted this earlier as well um about greedy future when the paper was really about greedy ass. That it's at best a two approximation. Remember? Uh this was uh okay, again, I would have to go back a lot of slides. Uh we've seen this little example which is not so far ago. That this greedy algorithm is at best a three half approximation. Um this is a very simple construction with a lot more work. You can show that there's a factor two at least in the worst case. Uh but we don't know. It could still be constant competitive.

39:12 Also known as dynamically optimal. Uh it's not not known.