Closest Pair of Points
Divide by x, recurse, then check the strip around the divider; O(n log n).
Decision · step 6 of 22Plane 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.
What you will see
Points split by a vertical line; only strip points are compared across the split.
Cost
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Points announce coordinates and role; each step announces the geometric test and its result in words (left turn, intersects).
Reduced motion: Shapes appear in place; the sweep line jumps between events.
Before this
Taught by the same lesson
Plane Geometry covers these too, in the same run.