Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

>> Now we'll look at an application of

sorting from the field of computational

geometry for an interesting computation.

If you have a set of N points in a

plane. There's a geometric object called

the Convex Hull which is the smallest

polygon that encloses all the points.

There's the Convex Hull for that set of

points. [cough] There's a lot of

equivalent definitions of this. Some of

them very mathematical, that extend the

higher dimensions. It's the smallest

convex set that contain all the points,

the smallest area of convex polygon

enclosing the points. It's a convex

polygon that encloses the points whose

vertices points in the set and those are

all equivalent definitions. And what we

want to do is given the set of points,

we're going to have a program that can

give us the convex hull. Now, which should

the output of such a program, such a

method be? Well, in order to be able to

work with the result, it should be a

sequence of vertices that gives us that

polygon if we follow it. If we've got some

points that are on the boundary but aren't

really vertices they shouldn't be

included. This points out examples of how

difficult computational geometry can

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

sorting from the field of computational

geometry for an interesting computation.

If you have a set of N points in a

plane. There's a geometric object called

the Convex Hull which is the smallest

polygon that encloses all the points.

There's the Convex Hull for that set of

points. [cough] There's a lot of

equivalent definitions of this. Some of

them very mathematical, that extend the

higher dimensions. It's the smallest

convex set that contain all the points,

the smallest area of convex polygon

enclosing the points. It's a convex

polygon that encloses the points whose

vertices points in the set and those are

all equivalent definitions. And what we

want to do is given the set of points,

we're going to have a program that can

give us the convex hull. Now, which should

the output of such a program, such a

method be? Well, in order to be able to

work with the result, it should be a

sequence of vertices that gives us that

polygon if we follow it. If we've got some

points that are on the boundary but aren't

really vertices they shouldn't be

included. This points out examples of how

difficult computational geometry can

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

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил