Closest Pair of Points
Divide by x, recurse, then check the strip around the divider. O(n log n).
Plane Geometry: Closest pair straddles the divider
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.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)
Before this
Related
Taught by the same lesson
Plane Geometry covers these too, in the same run.