Nearest Pair: Find the Closest Pair of Points in 2D Space

Problem Given N points in 2D space, find the pair with the minimum Euclidean distance. Example: A brute-force O(n^2) solution is expected first. Then discuss the divide-and-conquer approach. Approach Divide-and-conquer: sort by x, split at median, recurse on each half, then check the strip of width 2*delta around the midline. The strip check is O(n) because each point in the strip can have at most 7 neighbors within delta. Follow-ups Walk through the strip check. Why is the constant 7 (or 8) the…