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!