[MUSIC]. We are now starting the third week of our course in geometry. And this week we'll devote it to the problem known as line segment intersection. In this problem, in practice. As administrative temple, let us get back to geographic information systems once again. Suppose we seek to reveal the correlations between, say precipitation and vegetation, for certain regions of interest. Most likely, this kind of information will be stored in distant conceptual levels of our map. Thus, to retrieve the dependencies we're interested in, we will need to find the overlay of the respective maps. In site citation, we will inevitably need to find intersections of the boundaries of the regions of interest. And the boundaries will likely be represented by collections of straight line segments. Thus, the problem we are finally left with in the following. Given two or more sets of segments, we would like to find the two sections between the segments from different sets. But now, we will start with even a simple problem given just one set of segments. We would like to find all the intersection points of the segments from S. Now, we need to precisely indicate what an intersection point of two line segments is. We will define it as a common point of two closed line segments. This means that in all the three cases, you now see in the left of this slide. And namely, when two segments share a common interior point, when the endpoint of one segment lies inside the other one and when the two segments have a common endpoint, the respective two segments intersect. For the sake of simplicity, and we will emit from consideration the case when two segments overlap, and thus have an infinite number of shared points. However, after we develop the algorithm, it will be possible to slightly divide so as to incorporate such cases as well, and maybe you would like to do that at your discretion. Our goal is of course to develop an algorithm for solving this problem. Seemingly, a naive algorithm will solve it right away. Indeed, what we do is just checking all the pairs of segments from our set for pair-wise intersection. ,And whenever we find two segments that do intersect each other, we simply report the respective point. Since there are some particularly n squared pairs of segments, the time complexity of the naive algorithm will be also quadratic in the number of intersegments. Of course, this is not the first, and we might hope for finding a better algorithm. However, once again, the naive algorithm has even more serious drawbacks. Let us likely modify our sample set of segments as shown in this slide. We have just moved one segment, but now there are three segments in our set that all pass through the green point. However, the naive algorithm will not recognize this fact. Indeed, it will consider three pairs of segments defined by those three segments. And for each pair, output the intersection point for those two segments. Not only we want to have this kind of duplications in our output, but also, in practice, most likely, we would be interested in knowing precisely that one of the intersection points, either that for three or more segments. And this special case is not the only one that deserves special consideration. Let us introduce the international modification in our sample set of segments. As you can see on the left of the slide, we have shortened one of the segments, so that now its left endpoint falls inside the other segment from our set. In such a case, when finding the intersection point, we would also like to know that this very point represents an endpoint of one of the segments from our set. The observations we have just made will actually help us to properly formalize the problem we're going to address. The problem statement will be the following. Given a set S of n segments in the plane, we would like to find all the intersections of those. For each intersection point, we will need to report all the segments from S that pass through it. And for each segment passing through such intersection point, we will need to specify whether this point is its inner point or its endpoint.
