Closest Pair Algorithm Divide And Conquer

Closest Pair Algorithm Using Divide and Conquer

The closest pair problem asks: given a set of points in a plane, find the two points whose Euclidean distance is smallest. A naïve solution checks every pair, leading to (O(n^2)) time, which becomes impractical for large inputs. The closest pair algorithm divide and conquer improves this to (O(n \log n)) by recursively splitting the point set, solving sub‑problems, and then efficiently checking points that lie near the dividing line. This approach is a classic example of how clever recursion can dramatically reduce computational effort while preserving exactness.

Why the Divide‑and‑Conquer Idea Works

At first glance, splitting the points seems to lose information about pairs that straddle the two halves. That said, after solving the left and right halves we already know the smallest distance (d_L) and (d_R) inside each half. Practically speaking, the true answer can only be smaller than (\min(d_L, d_R)) if a pair consists of one point from the left side and one from the right side, and their distance is less than that minimum. Crucially, such a cross‑pair must lie within a vertical strip of width (2\delta) centered on the dividing line, where (\delta = \min(d_L, d_R)). Worth adding, within that strip each point needs to be compared only with a constant number of neighbors (at most seven) when the points are sorted by y‑coordinate. This observation turns a potentially quadratic check into a linear scan, preserving the overall (O(n \log n)) bound Nothing fancy..

Step‑by‑Step Procedure

Below is the full algorithm expressed in clear stages. Each stage builds on the previous one, and the recursion terminates when the sub‑problem size is small enough to solve by brute force That's the whole idea..

1. Pre‑processing – Sort by x‑coordinate

   • Input: array (P) of (n) points ((x_i, y_i)).
   • Sort (P) ascending by (x). Call the sorted array (P_x).
   • Why? Sorting enables a clean split into left and right halves by index.

2. Recursive Function closestPair(P_x, P_y)

   • Base case: If (|P_x| \le 3), compute all pairwise distances directly and return the minimum.
   • Divide:
     • Find the midpoint index (mid = \lfloor n/2 \rfloor).
     • Let (x_{mid}) be the x‑coordinate of (P_x[mid]).
     • Split (P_x) into left half (L_x = P_x[0..mid-1]) and right half (R_x = P_x[mid..n-1]).
   • Conquer:
     • Recursively compute (\delta_L = closestPair(L_x, L_y)) and (\delta_R = closestPair(R_x, R_y)).
     • Set (\delta = \min(\delta_L, \delta_R)).
   • Combine – Strip processing:
     • Build the array (strip) containing points from (P_y) whose x‑coordinate satisfies (|x - x_{mid}| < \delta). Because (P_y) is the original set sorted by y, this step is linear.
     • For each point (p) in (strip), compare it with the next up to 7 points in (strip) (also sorted by y). Update (\delta) if a smaller distance is found.
   • Return (\delta).

3. Auxiliary Array (P_y)

   • To avoid re‑sorting by y at each recursion level, we pass along a copy of the points sorted by y‑coordinate. When splitting, we partition (P_y) into (L_y) and (R_y) by checking each point’s x‑coordinate against (x_{mid}). This keeps the combine step linear.

4. Final Result

   • The value returned by the top‑level call is the smallest Euclidean distance among all point pairs. If the actual pair coordinates are needed, the algorithm can be modified to store the pair whenever a new minimum is discovered.

Complexity Analysis

• Sorting: Initial sorting by x and y each costs (O(n \log n)).
• Recurrence: Let (T(n)) be the time for the recursive part (excluding the initial sorts). The algorithm does:
  • Two recursive calls on halves: (2T(n/2)).
  • Linear work to build the strip and scan it: (O(n)).
    Hence, (T(n) = 2T(n/2) + O(n)).
• By the Master Theorem, this solves to (T(n) = O(n \log n)).
• Adding the (O(n \log n)) pre‑sorting steps yields an overall bound of (O(n \log n)) time and (O(n)) extra space (for the auxiliary y‑sorted array).

Implementation Tips

Common Pitfalls and How to Avoid Them

• Incorrect strip width: Using (\delta) instead of (2\delta) will miss valid cross‑pairs. Remember the strip must extend (\delta) on each side of the dividing line.
• **Neglecting y‑sorting in

Common Pitfalls (continued)

• Neglecting y‑sorting in the combine step: If you resort the strip by y at each recursive call rather than leveraging the pre‑sorted (P_y), the combine step degrades to (O(n \log n)), inflating the total complexity to (O(n \log^2 n)).
• **Off‑by‑

Common Pitfalls (continued)

• Neglecting y‑sorting in the strip scanning – The strip that is examined after the recursive calls must remain ordered by the y‑coordinate. If you re‑sort the strip at each level (for example, by calling Arrays.sort(stripY)), the linear‑time scan becomes (O(n \log n)) and the whole algorithm collapses to (O(n \log^2 n)). The key is to reuse the pre‑sorted P_y and simply filter the points that fall inside the vertical strip while preserving their order.

• Duplicate or coincident points – The algorithm assumes distinct points, yet real‑world data often contain duplicates. If two points occupy exactly the same location, the true minimum distance is zero. A cheap pre‑pass that checks for identical coordinates (e.g., using a hash set) can short‑circuit the computation and avoid endless recursion on degenerate sub‑problems.

• Choosing an inappropriate base case size – While the classic implementation recurses until a single point remains, many practical versions switch to brute force when the subarray size drops to a small constant (e.g., 3‑10 points). Selecting a threshold that is too small adds recursion overhead; picking one that is too large re‑introdu