Video 4-2: Planar Point Location via Persistence

0:04 Before we get to how to build persistent data structures, I want to show you an example that uses them in a very maybe surprising way or surprising context. Um that's uh just just shows you the idea is uh more versatile than the original formulation of the the idea itself. Uh that's the problem of of planar point location. Uh let me explain what that problem is. It's um it's from a a computational geometry perspective. So, it's it's um an algorithmic question about geometric objects. Planar means 2D. Um It's uh all that it says. And I'll explain what point location means. I want to mention that in this area, this is a very basic fundamental problem that people invented a handful of separate approaches for. You could say maybe it's a a bit like sorting for algorithms. This is for um for computational geometry data structures. So, the problem is is as follows. Um You have uh your two-dimensional space. I'm just drawing the box around to know show you where the image ends.

1:20 Um and then you have uh straight line segments. And here um the condition is that they may touch. So, they maybe form some shapes. But if they touch, then only at the endpoints. They don't cross. Now, this is in a way not even a severe restriction. It would just mean that this here if there is a crossing then um these line segments here, these are separate lines. There's one line for this part and one line for this part and they're completely independent. They just happen to lie on the same line and one extends the other. Uh but for the algorithm, these are independent lines.

2:10 Okay, so uh we have a a set of line segments. Uh I guess let's call this n. They only intersect if at all at the end points.

2:43 That's the input at the pre-processing step. where we're given uh a single point. And we try to find if I shoot a vertical ray upwards from this point, what green line do I hit if any? I could also have a query point here where I'm going on all the way up to infinity and I'm never going to hit anything. Um Now, this was maybe a bad example in the sense that there's nothing above it. Let's say put it here. So, there's three green lines, but I want the first that I hit. And of course, things are a bit more interesting if I'm somewhere in the middle of these of these lines. Um then I would still want to find this line, not the other one. And here in this case, I I report no line. There's nothing above me. Okay?

4:25 Now, this is in a way is a a primitive version of finding in which area the point lies. If you think about maybe an application would rather have various lines that divide the space into regions.

4:42 As long as these are polygons, they essentially consist of lines at the end of the day. And so these could be I don't know, cities of a map or whatever. If I want to find where a certain point is located in what uh region of the space. Uh I could either have define identity for the space or I could associate this with the line above it. If I know that it it is below this line, then I can somehow work my way back from this line segment is the upper um boundary of this areas of this uh region of the map. And then I can do whatever I need to do for that. Maybe find um for a point on on some map what's what council is it in. That's why it's such a basic problem. Now, how would you solve this? Uh one one easy idea or one one idea one may have um is to put just just to split up the space wherever there is a line segment such an endpoint I'm going to split my space up with a vertical line.

6:03 And now note within any of these vertical slabs there cannot be any intersections between any lines because by definition I've made a new slab whenever there was any crossing point. So within one slab if I only look at this this part here uh there's going to be some lines and another line uh and these will always be sorted. They'll stay in the same order. There's the lowest line and then the next and so on. Because if there were a change they would need to cross.

6:56 It's a very colorful topic. Um if the lines are sorted I can use binary search for my point here. So I could uh prepare for every vertical slab.

7:16 And these are known at preprocessing time right? I'm given all the line segments. So at preprocessing time for every slab I store the list of line segments that intersect that slab. May only be a few like here these two and I store them in sorted order by Y-coordinate.

7:52 Uh coordinate sounds like it's a single point, but really here it means the relative order cannot change. How do I find a point at query time?

8:11 Well, it consists of two steps. First, I use the X-coordinate. I guess this also belongs into the pre-processing step. I also have a a sorted list of the slabs, a sorted array of slabs So, um by using binary search on the positions here where the red lines touch touch ground, uh I find the slab that this blue point is in. That's easy. And this is uh log n time, uh where n n was the number of line segments. The number of end points is two times n, and there's no further crossing, so ignoring constant factors, in logarithmic time I can find the right slab. And second step, uh Uh let's continue in blue. Uh for this point Y. Now, uh what this means is I'm comparing a point to a line. You may wonder, how do I do that? That's a bit undefined. But really, whenever you compare a green line to the blue point, you know the X coordinate, so you can evaluate the line at that X coordinate.

9:56 It's a linear function, just compute the Y value, and then uh you can compute if the Y value you get is larger than your input Y or not.

10:23 So, you can do a binary search even even if the uh point you're given at query time is a different one each time. Uh how long does this take? Well, it's another binary search, and in every slab I can have at most all lines, so that's another log n. So, in total time log n, we can solve the query. That's great. Uh you'll see that this is essentially a uh the best one would hope for. But what is the preprocessing time or the the space requirement? So, for this part here, I need to keep the sorted list per slab.

11:05 And uh let's pretend we're in the worst-case scenario. So, my lines could be all merrily going across the entire X range. So, in the worst-case space usage is linear per slab.

11:41 And so, uh to even just produce this space, I need to spend that much pre-processing time. And it's indeed a bit more because I have to sort in each slab. And uh each slab is kind of sorted differently. So, that's the space.

12:08 And for the time, I get at least this uh log n factor for each of the slabs. So, in a way, okay, the query is fast, but the pre-processing time is slow. We can do better. And the reason why is um maybe even rather nice to see in this uh worst-case example.

12:32 If you look at two um if you look at two adjacent slabs, like these two, they'll they're going to be mostly the same. In a way, almost by definition, most of them will uh maybe there's a a crossing point if if the input is is awkward, then maybe there's several line endpoints at the same X coordinate. But then, I'm actually in the lucky case because I have fewer slabs than my input might otherwise give me. The kind of bad case in terms of number of slabs is the red points all have a different X coordinate. But then, from say, here is my X point at this at this uh coordinate, here's the one here, and here's the next one. If I go from from this slab to this slab, all that changes is that these two lines cross. And the order of all the others is the same. So, clearly I can avoid re-sorting all the time, right?

13:34 But if I have to store separately per slab all the lines, I'm not going to get below this space and hence I'm not going to get below n squared running time for the pre-processing. Because I have to write down all these lists. So, instead That's the observation here. Neighboring slabs don't differ much.

14:13 And we can even be more precise in if I move from left to right visiting each slab one after the other, the total number of changes is going to be linear in the number of line segments because for every change I have a red point.

15:00 So, if only we could somehow make use of that, right? Uh and the idea is uh to use we do a sweep line algorithm from left to right. What that means is visually you you take your configuration of lines or let me use the cleaner one from above.

15:49 Uh you move a line I theoretically You have this line that you move to the left to the right from left to right over the entire input. And whenever you see a red point, something happens. That's uh an event. And now in this sense, the X coordinate now becomes time because I'm moving over time through this picture. Whenever I see a red point, that either means a new line has arrived on the scene. So here I'm going to add two lines, line one and line two.

16:40 At this point, it's a degenerate event. There's two things happening at the same time. That's fine. And then at another event like this one, I'm going to remove one again. Because it now dies, right? This is the end of the line. And there's another line, say three, that's also removed here. Remove three. So these are events in a in a sorted dictionary. The dictionary is sorted by Y direction. Okay, so the uh and we make it a persistent binary search tree. So, all the old versions are still around even after we finished sweeping our line through this.

17:56 At these red dots, we do an insert or delete. Now, what is a version in this tree will um we'll come to in a second a bit more formally. Conceptually, uh it's just a a point in time here, but I can associate that with an X value. So, I can make a list of all the points where something changed. Keep that in a sorted list again.

18:32 The X values with versions. So, version you'll see in this case will just be a number. It's the number of updates in the tree. That's the preprocessing step. How long does it take? Well, that depends how efficient this partial this this persistent B-tree binary search tree is. And note that it is only partially persistent. We do updates at the last version, the current one where we are with our sweep line. And we're not going to need to change it. Um queries only do queries on this partial persistent tree.

19:16 First, we find the version using the X coordinate. And in that version, we query the tree for at that time, at that point in time, what was for my Y coordinate the next largest line?

19:36 And in a way, this is a successor query, if you Uh say this is called V, the version we find there. Uh And uh again, um without knowing how efficient you can build persistent data structures, you can't really know how fast this is. Uh the the result in the end will be that in this case, the persistence is for free up to constant factors.

20:10 So, you can still do each of the update steps in logarithmic time in a balanced binary search tree, which means here we'll have n log n time total.

20:31 And so far, this is a promise, okay? You can't know. Um but then, this is a standard binary search. That's clearly logarithmic in the number of versions. And the query, by my promise, is also unchanged up to constant factors. So, that's another log n. So, in terms of uh the query time, we have the same complexity as before, but the update uh the the preprocessing time is now a factor n faster. Okay? And what we've done is essentially take one dimension of the space and turned it into And with that, uh we could essentially, by looking back in time, uh get rid of one dimension, which makes geometry easier if it's on one dimension.

21:23 That's the motivation, or one motivation, for these persistent data structures. Of course, there are obvious others. In particular, databases often want to keep past versions around. They may even want full persistence, but partial persistence is often good enough.