Divide and Conquer: Closest Pair of Points

The Problem and the Brute-Force Baseline

The problem statement is simple: given a set of $n$ points on a 2D plane, find the pair of points with the smallest Euclidean distance between them.

The most straightforward approach is to calculate the distance between every possible pair of points and keep track of the minimum distance found. Given your software engineering experience, you'll recognize this as a nested loop structure. With $n$ points, there are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$ pairs, leading to an $O(n^2)$ time complexity.

For a small number of points, this is fine. But as $n$ grows, $n^2$ quickly becomes impractical. Can we do better? Since this lesson is in the Divide and Conquer module, the answer is a resounding yes. Our goal is to achieve an $O(n\log n)$ solution.

Structuring a Divide and Conquer Solution

Let's apply the D&C framework we learned previously.

1. Divide: The most intuitive way to split a set of 2D points is to draw a vertical line that divides them into two roughly equal-sized subsets: a left half ($P_L$) and a right half ($P_R$). To do this efficiently, we can presort all points based on their x-coordinate and find the median point. This dividing line will pass through that median point.

2. Conquer: We make two recursive calls: one to find the closest pair in $P_L$ and another for $P_R$. Let's say these calls return minimum distances of ${\delta }_L$ and ${\delta }_R$, respectively.

3. Combine: After the recursive calls, we know the closest pair distance is at most $\delta =\min ({\delta }_L,{\delta }_R)$. However, the true closest pair might consist of one point from $P_L$ and one from $P_R$. This "crossing pair" is the crux of the problem.

To find this crossing pair, we don't want to revert to an $O(n^2)$ check. This is where the geometric insights begin.

The "Combine" Step: Finding the Crossing Pair

The key observation is that if a closer pair $(p_L,p_R)$ exists, where $p_L\in P_L$ and $p_R\in P_R$, its distance must be less than $\delta$. This implies that both $p_L$ and $p_R$ must lie very close to the dividing line. Specifically, both points must be within a distance of $\delta$ from the vertical line.

This insight allows us to restrict our search to a vertical "strip" of width $2\delta$ centered on the dividing line.

The following video provides a clear, visual walkthrough of the brute-force method, the D&C setup, and this critical concept of the $2\delta$ strip.

The Critical Optimization: Searching the Strip

We've narrowed our search to the points within the $2\delta$ strip. However, in the worst case, all $n$ points could lie within this strip. A naive comparison of all points in the strip would still lead back to an $O(n^2)$ complexity for the combine step. We need one more crucial insight.

Consider a single point $p$ in the strip. We need to find if there's any other point $q$ in the strip such that their distance is less than $\delta$.

1. To make this search efficient, we will process the points in the strip sorted by their y-coordinate.
2. For a given point $p$, any potential matching point $q$ must have a y-coordinate "close" to $p$'s y-coordinate. Specifically, their vertical distance must be less than $\delta$. This means we only need to check points in a $\delta \times 2\delta$ rectangle centered at $p$.

The magical part is this: how many points can possibly exist in that rectangle?

Recall that any two points on the left side of the dividing line are at least $\delta$ apart, and the same is true for any two points on the right. This constraint prevents too many points from being packed closely together. It turns out that for any point $p$, we only need to check a small, constant number of subsequent points in the y-sorted strip.

The proof for this is a beautiful geometric argument. Let's watch a detailed explanation.

The key takeaway from the video is that the region around point $p$ can be divided into small squares. Because we know the minimum distance within each half is $\delta$, we can prove that at most one point can occupy each small square. This limits the total number of points to check to a small constant (different analyses yield numbers like 6, 7, 8, or 15, but all are constant).

This means the "Combine" step, which seemed like it could be $O(n^2)$, is actually only $O(n)$. We iterate through the $O(n)$ points in the strip, and for each, we do a constant number of comparisons.

For a more formal, text-based proof of this property, you can refer to the resource below, which is an excerpt from the classic CLRS algorithms textbook. It proves that checking the next 7 points is sufficient.

The Full Algorithm and Its Complexity

Now, we can assemble the complete algorithm and analyze its runtime.

Algorithm: Closest-Pair(P)

1. Presort: Create two lists of the input points: Px sorted by x-coordinate, and Py sorted by y-coordinate. This takes $O(n\log n)$.
2. Recursive Function Closest-Util(Px, Py):
   • Base Case: If |Px| $\le$ 3, solve by brute force. Return the minimum distance.
   • Divide: Find the median x-coordinate to partition Px into Px_L and Px_R. Partition Py into Py_L and Py_R by iterating through Py and checking if a point's x-coordinate is in the left or right half. This takes $O(n)$ time.
   • Conquer: Recursively call d_L = Closest-Util(Px_L, Py_L) and d_R = Closest-Util(Px_R, Py_R). Let $\delta =\min (d_L,d_R)$.
   • Combine:
     a. Create a strip array containing points from Py whose x-distance from the dividing line is less than $\delta$. This strip array remains sorted by y-coordinate. This takes $O(n)$.
     b. For each point p in strip, calculate its distance to the next ~7 points in strip. Update $\delta$ if a smaller distance is found. This takes $O(n)$ time because the inner loop is constant.
   • Return $\delta$.

The following video segment quickly recaps the algorithm and its complexity analysis.

Complexity Analysis

• The initial sorting takes $O(n\log n)$.
• The recurrence relation for our recursive function is $T(n)=2T(n/2)+O(n)$.
  • $2T(n/2)$ comes from the two recursive calls on halves of the data.
  • $O(n)$ comes from the linear-time work in the Divide (splitting Py) and Combine (creating and scanning the strip) steps.

As you'll recall from our first module, this recurrence solves to $T(n)=O(n\log n)$. Therefore, the entire algorithm is dominated by the presorting and the recursive part, resulting in an overall time complexity of $O(n\log n)$.

Conclusion

In this lesson, we successfully applied the Divide and Conquer strategy to a non-trivial geometry problem. We saw that while the "Divide" and "Conquer" steps were relatively straightforward, the "Combine" step required significant ingenuity. By using a clever geometric argument, we reduced the work in the combine step from a potential $O(n^2)$ to a much more efficient $O(n)$, enabling the entire algorithm to run in $O(n\log n)$ time.

Key Takeaways:

• The Closest Pair of Points problem can be solved in $O(n\log n)$ time using a Divide and Conquer approach.
• The "Combine" step is the most critical part of the algorithm's design.
• The search for a closer "crossing" pair can be restricted to a $2\delta$-wide vertical strip.
• Within this strip, a geometric proof guarantees that for any point, we only need to check a constant number of its neighbors (when sorted by y-coordinate). This is what makes the combine step linear.
• Presorting points by both x and y coordinates is a crucial implementation detail for achieving the desired time complexity.

Preview of the Next Lesson:

We have now explored two powerful applications of Divide and Conquer. Next, we will shift our focus to another fundamental algorithmic design paradigm: Greedy Algorithms. While D&C solves subproblems and then combines their results, a greedy algorithm makes a sequence of locally optimal choices with the hope of arriving at a globally optimal solution. We will begin by exploring the core properties of problems that are solvable with a greedy approach.