Closest Pair of Points
Learn Closest Pair of Points (Divide & Conquer, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Closest Pair of Points Given n points in the plane, find the two that are closest together . Comparing all pairs costs O(n²) . Divide and conquer does it in O(n log n) : sort the points by x, split them with a vertical line, find the closest pair d inside each half, then check the pairs that cross the line . Only points within distance d of the line matter, and each needs to be compared with just a few neighbours.