If we’re given a set of points that lie on a plane, how can we figure out which pairs are the closest pair of points on the plane? The points are frequently stored in an array. One approach is to take the divide and conquer method. How? By following the steps below:

• Count the number of points on the plane.
• Divide the points into two equal groups and draw a line through the middle. If there are an odd number of points, a line will go through at least one of the points.
• Get the smallest distance between two points on the left and the smallest distance between two points on the right.
• Whatever the smallest distance is, δ, create an area to the left of the midline and to the right of the midline that’s equal to that distance.
• Start at the bottom of the newly created area and compare the points that are on the left with the points that are on the right. Note, not all points have to be compared.

Let’s look at an example. We have a plane with 16 points.

Step one says to draw a line down the middle so that the left plane and the right planes can be created. There are 8 points on the left and 8 points on the right.

Next, we’ll find the closest pair of points on the left and the closest pair of points on the right.

Next, we’ll find the smallest distance of the two. Since they’re both equal to 2, we’ll set δ = 2. An area to the left of the midline with δ = 2 is shaded as well as an area to the right of the midline.

We’ll start with the bottom point and move our way up. Only points that are not in the same area will be compared since the points that are in the same area have already been compared. Comparing the bottom point with the point next up in the opposite side yields a distance of 3. That point will not be included. There’s no point in comparing other points from the bottom point since we already know that they’re further away.

We move to the second point.

The next closest point to the second point is in the same region, so we move to the third point. The next closest point on the opposite side is 2 units away. Since it’s within the smallest distance constraint, we’ll include that point in calculating the closest distance between points.

We move to point 4 and find the distance to point 5 on the left. The distance is 5 so that path is excluded.

Finally, we find the distance from point 5 on the left to point 6 on the right. The distance is 3, so that path is excluded as well.

We reach the final point. There are no additional points that we can find the distance to, so the algorithm ends. The closest distance between two points is 2.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.