AlgoScope

Closest Pair of Points

Divide by x, recurse, then check the strip around the divider. O(n log n).

Computational geometry, algorithm, advancedAlso called Closest Pair (divide and conquer)
Strip of 4 points around x = 2.ABCDEFGH
Strip of 4 points around x = 2.ABCDEFGH

Plane Geometry: Closest pair straddles the divider

Decision, step 6 of 22

Both sides done. The best distance so far is 4.1. A closer pair that straddles the divider would need both points within 4.1 of x = 2. That strip holds B, D, A, C, taken in y order.

How plane geometry works

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

Taught by the same lesson

Plane Geometry covers these too, in the same run.