Closest Pair of Points

← Back to Divide and Conquer

Find the two closest points in a set of points in the plane. The divide-and-conquer approach splits points by x-coordinate, recursively solves each half, and efficiently checks the strip near the dividing line. O(n log n) time, improving over the O(n^2) brute-force approach.

algorithms divide-and-conquer closest-pair