Posted by: atri | November 19, 2012

Lect 33: Closest Pair of points

Today we looked at the problem of computing the closest pair of points in a given set of n points in the plane. We started designing a divide and conquer algorithm. Next lecture, we will look at the final patchup problem that we need to solve. (I.e. computing the shortest pair of points with x-value in the range [x^*-\delta,x^*+\delta]. All this material is from Section 5.4 in the textbook. If you missed today’s lecture, please make sure that you read up on today’s stuff from the book for Monday’s lecture.

The slides and notes have been uploaded.

Have a good Thanksgiving break!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: