0:02

So now let's look at a basic geometric data processing problem of determining

intersections among a set of line segments. So, it's called the orthogonal

line segment, segment intersection search where the lines segments or constrained to

be either horizontal or vertical. And so, suppose we have a large number of such

line segments and what we want to be able to do is to find all places where they

intersect. And as we'll see this extends to a practical problem in a number of

situations. So, in this case there's four places where these lines intersect. So,

how are we going to be able to determine these intersections efficiently? Now, the

natural algorithm, or the naive brute-force algorithm, is quadratic in

time. So that is, for every line segment, you check whether it intersects with every

other line segment. And again, as we know, such an algorithm is not going to be

practical, for huge numbers of line segments. So, just, to simplify our code

in the slides in it's off, off from the case for geometric data processing. We

don't have to worry about degeneracies where lots of things have the same x or y

coordinate. And just to simplify the code and to get it the main principles of the

algorithms, we're going to assume that all the coordinates that we have are distinct

that we've preprocessed in some way to remove the ones that touch without

intersecting. So the method that we're going to look at is a so called Sweep Line

algorithm and the idea is to think of vertical line that sweeps left to right

through the data. In to. Consider it as a every time it hits some line segment as an

event where we have to do something. So sweeping from left to right means we

consider each x coordinate as an event. So first thing is if we hit a horizontal line

segment. Well we're going to hit the left endpoint first, and so what we'll do when

we hit the left, endpoint is, insert, the y coordinate of that line into a binary

search tree. So, we're going to keep track of y coordinates in a binary search tree.

So that's what's happening over in the right there. So now again, sweep from left

to right. What's the next smallest x coordinate? In this case it's the line

number one there, and we'll remember its y coordinate in a binary search tree. And

then two and three. So those that's one kind of event that can happen as we sweep

from left to right. Another kind of event is that we hit the right endpoint of a

horizontal line segment. In this case we hit the right endpoint of line segment

two. So, at that point the right point of a horizontal line segment we just remove

it because we've processed that line completely. In this case we didn't find

any intersections. So, left endpoint insert the y coordinate into a BST, right

endpoint remove that ycoordinate from the BST. So, the BST contains the y

coordinates of all the horizontal lines that currently might involve an

intersection. And then the third kind of event is what happens when we hit a

vertical line segment? Well, in that case all we want, need to do is just do a range

search, for the interval of y end points. So, any point that's inside that interval,

is going to represent a horizontal line segment that is an intersection. That's

the basic idea behind the sweep line algorithm, to find intersections in sets

of horizontal and vertical lines. And it's actually a very simple algorithm, and it's

very easy to see that the running time is going to be proportional to N log N plus

the number of intersections returned. Where there's N horizontal vertical line

segments. And it's, and a couple of ways to implement it, one thing is you could

sort according to the x coordinates, or you could just put them all on a priority

queue. And then, so, so that's going to take N log N for every one of the lines to

process them all either N to build the priorit y queue and then log N to take the

smallest off each time, or N log N for the sort. And then putting the y coordinates

into, into a binary search tree is, again, N log N. And same for deleting. Each point

has to be inserted, deleted. It could be as many as N in the tree for each one. So

it's a total of N log N. And then the, range search, in the binary tree, for

each, each one of the range searches. It might take, log N, it might be as many as

N. And then there's, plus the number of points return. So, That's a, quick sketch

of the proof of this proposition. And with that 1D range search, implementation, we

get an efficient N log N, 2D orthogonal, orthogonal line segment, intersection