Closest Pair Problem
The closest pair problem finds the minimum distance between any two points in a set of points in the plane. A naive O(n²) algorithm checks all pairs. Using divide and conquer, we can achieve O(n log n).
Algorithm:
1. Sort points by x-coordinate.
2. Recursively find the smallest distance in left and right halves.
3. Let d = min(d_left, d_right).
4. Consider points within d of the dividing line (strip).
5. Sort those points by y, and check distances between points within d (only need to check a limited number).
Java implementation outline:
public static double closestPair(Point[] points) {
Arrays.sort(points, (a,b) -> a.x - b.x);
return closestPairRec(points, 0, points.length - 1);
}
private static double closestPairRec(Point[] pts, int left, int right) {
if (right - left + 1 <= 3) return bruteForce(pts, left, right);
int mid = (left + right) / 2;
double dl = closestPairRec(pts, left, mid);
double dr = closestPairRec(pts, mid + 1, right);
double d = Math.min(dl, dr);
// strip points near the midline
List strip = new ArrayList<>();
for (int i = left; i <= right; i++) {
if (Math.abs(pts[i].x - pts[mid].x) < d) strip.add(pts[i]);
}
strip.sort((a,b) -> a.y - b.y);
for (int i = 0; i < strip.size(); i++) {
for (int j = i+1; j < strip.size() && (strip.get(j).y - strip.get(i).y) < d; j++) {
d = Math.min(d, distance(strip.get(i), strip.get(j)));
}
}
return d;
}
Two Minute Drill
- Closest pair problem finds minimum distance between points.
- Divide and conquer: O(n log n).
- Combine step uses a strip and y-sorting.
- Only O(n) points need to be checked in the strip.
Need more clarification?
Drop us an email at career@quipoinfotech.com