1:32

sometimes be because degenerate cases like these are difficult to deal with in

Â code. We're not going to spend a lot of time on this, in this lecture. But it's

Â something always to be aware of when trying to [cough] apply simple algorithms

Â in situations like these that turn out to be maybe more sophisticated than we might

Â think. >> [inaudible] the large screen.

Â >> Oh yeah, got you. Mm-hm. Well, there's actually a way to compute the convex hull

Â just mechanically if you put the nails around the points and put a rubber band

Â around it, that gives you the convex hull. Now, we're not going to be able to really

Â implement that in a computer program but it's surprising how well we can do. Here's

Â an application where people want to compute the convex hull. Suppose you have

Â a robot that wants to get from s to t and there's an obstacle that's defined by some

Â polygon. You wanted be able to go around the obstacle and it turns out that the

Â shortest path, either it's a straight line from s to t or it's part of the convex

Â hull and is not hard to see why that might be true. And there's plenty of other

Â applications where people want to be able to compute the convex hull. Here's another

Â application. If you want to find the pair of points that are the farthest apart in

Â the set of points in the plane, this is sometimes important in statistical

Â calculation or other applications. They're on the convex hull. If you have the convex

Â hull, this computation is easy. [cough] They're, they're going to be extreme

Â points on the convex hull. So, there's a lot of geometric properties of the convex

Â hull that we can take advantage of to develop an algorithm. In here two

Â properties. Now, these are the things that have to be proven and we're not going to

Â get into the details of geometric proof but they're intuitive and certainly have

Â no trouble accepting that these things are true. One thing is, that you can traverse

Â the convex hull by making only counter clockwise turns or left turns if you're

Â looking at the screen here. And the other thing is that, so if we travel from p to

Â point 1 then we make a left turn to go to point 5 or counterclockwise turn and

Â then from there, we go to point 9 and 12 and then we eventually get back to

Â the start point. The other thing is, if you take the point with the lowest y

Â coordinate. And then if you look at the polar angle with respect for every other

Â point with the respect to that one, so the angle you get from of the x-axis through p up to

Â the point, then the vertices appear in increasing order of that angle. And again,

Â that's not, not difficult to see that that's a fact. And the algorithm that

Â we're going to look at, called the Graham scan is based on those two facts. It's,

Â the idea is to start with point p, the one with the smallest y coordinate. Sort

Â the points by polar angle with p where that is we're just going to consider in

Â that order. And then we'll just throw away the ones that do not create a

Â counterclockwise turn and you'll see how that works when we look at the demo. So we

Â start at point p. Sort the points by polar angle with p so that is if we take a, a

Â vertical line and sweep it in a counterclockwise direction, what order

Â that we hit the points? The first thing we hit is 0, 1, and then we sweep

Â counterclockwise, we get the 2 and then 3 and 4 and so forth. So, that's

Â the ordering of those points. And so now we'll just consider those points in order

Â and then take them for the convex hull. At the beginning, 0->1 is a line that's

Â on the convex hull. So, the point with the lowest y coordinates on the convex hull

Â and shows the one that is the smallest polar angle that creates with the x-axis.

Â So now what about this one - 2? Is that on the convex hull? Well, as far as we know

Â at this point, it could be, it could be that the thing is a triangle and 0 is

Â the last point in which case it would be. But in same with 3. As far as we know,

Â that one could be on the convex hull. But as soon as we go out to 4 that's not a

Â counterclockwise turn. It's going the wrong way and essentially what this means

Â is a point 4 is evidence that point, there is no way the point 3 can be on

Â the convex hull. You can [cough] convince yourself with that quite easily. So we

Â just throw a point 3 out. It's not on the convex hull so, and what about the

Â angle from 1 to 2 to 4? That's not counterclockwise either. It's turning the

Â wrong way and it's turning to the right. So point 2 can't be on the convex hull

Â either. And indeed if you just draw the line from 1 to 4, you can see the 2

Â inside so there is no way it could be in the convex hull. Now that's essentially

Â the proof that you have to have a counterclockwise turn. So now, we go on to

Â 5 - turning the wrong way. So, point 4 can't be on the convex hull. So now we go

Â to 6. As far as we know, it could be, but as soon as we hit 7, we know that it

Â can't be cuz that's a right turn. So 6 is not there. Go to 8, nope. 7 can't

Â be on the convex hull. Go to 9. 8 can't be on the convex hull. Now we go to

Â 10 and 11. As far as we know they could be. If 12 weren't there, they

Â would be. As soon as we hit 12 we see that 11 can't be on the convex hull

Â and 10 can't be on the convex hull and that completes the computation of the

Â convex hull with the Graham Scan. Okay. So, there are number of implementation

Â challenges for the Graham Scan and we're not going to go into detail on this

Â because this is a lecture on sorting algorithms not computational geometry but

Â it is indicative of how, even if we have a good sort, we might have to do some extra

Â work to actually solve our problem in an application. So, how do we find the point

Â with the smallest y coordinate? Well you could, you could sort, you could define an

Â order and compare the points by y coordinate so essentially sorting is the

Â [cough] answer to that question. And we'll look at the next lecture of what it means

Â the divine ordering among objects, little more general than what we do for sorting.

Â How to sort the points by polar angle? Well again we need to define what we mean

Â when we're comparing points. And then the next lecture again we'll look at ways to

Â define different orderings among points and Graham scan is a perfect example. We

Â don't want to just be able to sort things, we don't want to just be able to sort them

Â by defining and compared to. We're going to be able to sort the same things in

Â different way sometimes and this example is a fine motivation of that. Figuring out

Â whether what we have is a counter clockwise turn that's a little exercise in

Â geometry and we'll just talk about that briefly in the next couple of slides. And

Â then wow, what are we getting the sort efficient, done efficiently? Well, we

Â could use Shellsort but actually in the next couple of lectures and we'll look at

Â classical sorts - Mergesort and Quicksort - that we could use. The idea though is that

Â this example illustrates that good sorting algorithm gives us a good convex hull

Â algorithm. That's an extremely important principle in designing good algorithms.

Â Once we have a good algorithm, if we have another problem we can say to ourselves,

Â well, we've got a good solution to this algorithm, can we use that solution to

Â solve our new problem? Convex hull, when we have a good sorting algorithm, it gives

Â us a good convex hull algorithm. Because the main, the most work in convex hull is

Â the sort. And then again there's all, all kinds of difficulties in implementing

Â convex hull in real world situations because of various degeneracies. And these

Â things are covered on the book site. So the main part of computation that we

Â haven't really talked about and we'll cover briefly is if we have three points,

Â a, b and c, and you go from a to b to c, are you making a counterclockwise turn or

Â not? So, in the example at the left, a to b to c is counterclockwise. Example at the

Â right, a to b to c is not counter clockwise. Going from a to b you turn left

Â to get to c in the first case and you go right to get to c in the second case and

Â we want to do a computation that distinguishes this. Now, this computation

Â will be pretty easy except for the degeneracies. What do you want to count if

Â they're all on the same line. Or if the slope is infinity. So, you have to just be

Â aware that these situations have to be dealt with. So, the code isn't quite as

Â simple as you might come up within the first instance that you try. So, there's

Â degeneracies to deal with and floating point precision but people, researchers in

Â computational geometry have worked this out and actually there's not that much

Â code at all in the end involved. The and this is the slide that, that gives the

Â math and I won't talk through this math. If you're interested in implementing this,

Â you can come back to the slide. And it's essentially based on the idea of computing

Â the slopes of the lines between a and b, between a and c and comparing them to

Â decide whether you're turning counter clockwise or clockwise. And this is the

Â specific math that gets that implemented. So [cough] this is if we implement a point

Â data type for computational geometry, you can have a method ccw() that just with this

Â little math calculation (b.x - a.x)(c.y - a.y) minus (b.y - a.y)(c.x - a.x) and we

Â see that calculation here gives you immediately whether it's counter

Â clockwise, clockwise or co-linear. Not much code at all. And that method is the

Â basis for the Graham Scan. The Graham Scan uses a sort where we give two different

Â ways to sort the points. And that uses a push down stack for the hull, it puts the

Â points on the hull in it goes ahead and for every point considering I'm in the

Â order of the polar sort it'll compare whether the top two points on the hull and

Â the new point implement a CCW turn or not. And if it's not a CCW turn, it pops and

Â then continues going. Very little code to implement the convex hull given that you

Â have a sort and that's our main point for this lecture - there is many natural

Â applications of sorting but also will be able to develop new algorithms that use

Â sort that gain efficiency because of the efficiency of sorting.

Â