Now that we know what characterizes a divide and conquer algorithm and are familiar with the master method to derive bounds from recurrences, let's look at a problem solvable by a divide and conquer approach.

The problem we will be looking at is the problem of finding the closest pair of points on a plane. We are given an array of n points in the plane, and we want to find out the closest pair of points in this array. Recall that the distance between two points, p and q, is given by the following:

Our first approach may be to compute the distance between each pair and return the smallest, for a runtime complexity of O(n²). The following snippet implements this algorithm:

PointPair bruteForce(List<Point> points) {
  PointPair best = new PointPair(points.get(0), points.get(1));
  for (int i = 2; i < points.size(); i++) {
    for (int j = i - 1; j >= 0; j--) {
      PointPair candidate = new PointPair(points.get(i), points.get(j));
      if (candidate.distance() < best.distance())
        best = candidate;
    }
  }
  return best;
}

The proposed algorithm solves this problem, but we can do better by using a divide and conquer approach. The algorithm makes use of a preprocessing step in which it sorts the input array by its x coordinate. Then, it proceeds as follows:

1. Divides the array into two halves
2. Recursively finds the smallest distances in both subarrays (conquer)
3. Combines the results by taking the minimum distance from both halves and additionally considers pairs so that one point in the pair is from the left subarray and another is from the right subarray

The approach seems straightforward, except for the combine part. After finding the minimum distance d from both the left and right subarrays, we have an upper bound of the minimum distance for this subproblem. Therefore, we only need to consider points whose x coordinate is closer than d to the middle vertical line. We can then sort those points by y coordinates and find the smallest distance in the strip, as shown in the following diagram:

The following code snippet computes the minimum distance in the strip, considering the minimum distance computed so far:

Collections.sort(sortedPoints, (o1, o2) -> Integer.signum(o1.y - o2.y));
for (int i = 0; i < points.size(); i++) {
  for (int j = i + 1; j < points.size() &&
    (points.get(j).y - points.get(i).y) < best.distance(); j++) {
     PointPair candidate = new PointPair(points.get(i), points.get(j));
     if (candidate.distance() < best.distance())
       best = candidate;
  }
}

Looking at this code, it seems to have a runtime of O(n²), which doesn't really improve our brute force approach. However, it can be proved geometrically that for every point in the strip, a maximum of seven points after it need to be checked. This reduces the runtime of this step to O(nlogn) due to the sorting step.

We can even do better on this step if we sort the initial input by the y coordinate and keep a relationship between the points on the x-sorted array and the y-sorted array, effectively reducing the runtime of this step to O(n).

After having computed the minimum distance from both subarrays and the middle strip, we have found the closest pair of points in the subarray. The following code snippet exposes the merging part of both subarrays and calling the bestWithStrip() method:

PointPair bestSoFar = bl;
if (br.distance() < bl.distance())
  bestSoFar = br;
List<Point> strip = new ArrayList<>();
for (int i = 0; i < N; i++) {
  if (Math.abs(points.get(i).x - midPoint.x) < bestSoFar.distance())
      strip.add(points.get(i));
}
return bestWithStrip(strip, bestSoFar);

The proposed algorithm divides all points into two sets and recursively solves both subproblems. After dividing, it finds the strip in O(n) time and finds the closest points in O(n) time (we're assuming the improvement of not requiring the sort in this step). Therefore, T(n) can be expressed as T(n) = 2T(n/2) + O(n) + O(n) = 2T(n/2) + O(n), which is a bound of O(nlogn), being better than the brute force approach.