Lesson 38.3 · Advanced Search and Divide & Conquer
Closest Pair of Points and Splitting Expressions
Split the points by x, solve both halves, then check only a thin strip around the split line. Expressions split at every operator, combining results from both sides.
12 min
Think of it like this
Two neighbouring towns each know their own closest pair of houses. The only pairs they might miss straddle the border, and only houses near the border can be closer than the best already found.
1.The strip argument
Sort by x and recurse on halves to get the smaller best distance d. A closer pair must cross the middle line, so both points lie within d of it. Inside that strip, sorted by y, each point only needs comparing with the next few points (at most 7), so the combine step is linear. Total O(n log n).
Expression splitting (Different Ways to Add Parentheses): for each operator, compute all results of the left part and of the right part recursively, then combine every pair. Memoising by substring avoids repeated work.
Remember
- Combine step is the hard part.
- Only the strip near the split matters.
- Memoise repeated sub-expressions.
Common mistakes
- Comparing every pair in the strip without the y-sort bound (back to O(n²) worst case).