0:01

To finish up, we're going to look at the rectangle intersection problem that's got

Â important practical applications and, uses the techniques that we've been studying so

Â far. And it's a simple generalization of our line intersection problem. So now, we

Â have a bunch of rectangles. They're all oriented horizontal or vertical. And what

Â we need to do is find all the intersections in that set of rectangles.

Â And again N could be huge in applications, as we'll talk about in a second. And the

Â [cough] Naive Brute-Force Algorithm involves checking each pair of rectangles

Â for intersection. And what we want is a more efficient algorithm than that as

Â usual. And again, to keep the code simple we're going to assume that all the

Â coordinates are distinct. We don't have any, any equal lines that we have to worry

Â about whether we consider rectangles that touch to be intersecting, and so forth. So

Â that's, that's the problem, rectangle intersection search. This is historically,

Â an extremely, important problem. In the 1970s, when we switched to very large

Â scale integration for computers, we were switching from a situation where we were

Â wiring physical devices together, to a situation where we were essentially

Â drawing the computer. And there were machines that would take drawings and, and

Â return, [cough] and from those drawings, like this, make, physical things that

Â implemented computers with different layers and different, physical materials

Â interacting, in different ways. Some things are wires, and some things are

Â switches that, are used to, implement memory bits and computer logic. But the

Â key point about it is that designing a computer became a geometric problem. And

Â so, people, to design new computers, would, make huge drawings that just showed

Â the lines that corresponded to the materials that had to be created to make

Â the computer. Now, it was very expensive. You didn't want to have any bugs when

Â you're making a chip. And, there were various rules about what you can do on

Â these drawings. And basically, these rules had to do with doing this ortho,

Â orthogonal rectangle intersection search. You, you can't have [cough] lines that

Â come too close to other lines, certain types of lines can't intersect. Need

Â spacing between certain types of wires and, you wanted to, before you tried to

Â make the physical circuit to do this checking, which involved this orthogonal

Â rectangle intersection sort. And it was actually the case that the progress of

Â faster and faster processors with more and more components was slowed because people

Â were using the naive quadratic algorithm to do this design rule checking. And its

Â example of, of Moore's law. So, as we built a faster computer say, in 1970X, we

Â needed to check in rectangles. But now, maybe a year and a half later, you have a

Â computer that's two times faster but you also want to build a bigger computer so

Â you have twice as many rectangles to check. So you have two end rectangles to

Â check now, and your computer's twice as fast. So, we get to use the faster and

Â bigger computer to build faster and bigger circuits but that doesn't help if you're

Â using a quadratic algorithm. If you're using a quadratic algorithm and it takes

Â you n days to check your design rules, and people were running these things on the

Â order of days, then for the next computer, it would take 2n days, it would take twice

Â as long. And so people that were using quadratic algorithms were definitely held

Â back and, it was, Ed, Ed McCreight at Xerox Park who, discovered interval search

Â trees and the logarithmic algorithm that allowed us to sustain Moore's law and keep

Â building bigger and bigger computers. By changing this quadratic algorithm to a

Â linear logarithmic algorithm, and let's see how it works. Really, it's a

Â modification of the sweep line algorithm that we looked at for intersecting lines.

Â But now we're going to use that for intersecting rectangles rather than using

Â range search as our basic operation, we're going to use interval search. So now,

Â every time the line sweep hits a rectangle, that corresponds to an

Â interval. If it's the left part of a rectangle, then we put that interval into

Â our interval search tree. So in this case we put on zero and then we put on one and

Â then we put on two. And, and that will give us now three rectangles on our sweep

Â line. And so now, the question is when we hit a, a new rectangle, we want to do an

Â interval search to, if we're at the left to check which ones intersect and the

Â interval search tree algorithm is going to tell us which intersections there are

Â right away. When we reach the right then we remove intervals and so forth. But with

Â the basic interval search tree algorithm and the sweep line process that we've

Â talked about, you can get the orthogonal, orthogonal rectangle intersection search

Â problem solved in time proportional to analog N log N + R log N, where R is the

Â number of intersections. And typically, in design rule checking, you wouldn't expect

Â too many intersections. So again, just as with, line intersection search, using a

Â priority queue or a sort is only N log N for processing the X coordinates. And

Â because the interval search trees take log N for every operation, the insert and

Â delete intervals is N log N totaled and the searches is N log N + R log N. So, the

Â bottom line is that the sweep line algorithm takes this rectangle

Â intersection problem and reduces it to 1D interval search and we have an efficient

Â algorithm for that problem and that enables us to solve the problem in linear

Â rhythmic time instead of quadratic time. And that definitely enabled new progress

Â in technology and it's a fine example of the importance of algorithmic technology.

Â So here's our summary of applications of binary search trees for geometric

Â problems. We started with one dimensional range search and just used regular binary

Â search tree to compute ranks to get the answer. But that as the basis, we're able

Â to solve the two dimensional line segment intersection search using the sweep line

Â algorithm. Then we looked at range search and other operations using KD trees.

Â Again, modification of binary search trees. And then the interval search tree

Â to solve the one dimensional N over search problem and then how that corresponds to

Â the basic algorithm that you get to if you use the sweep line algorithm to solve

Â rectangle intersection. Many of these problems are the basis for geometric

Â processing of huge amounts of data that we see all over the web. And our basic search

Â tree mentality and APIs, and binary search tree data structure give us efficient

Â solutions to these important practical problems.

Â