In the divide and conquer closest pair of points algorithm, the strip step compares each point only with a constant number of following points in the y-sorted strip. Prove that constant is bounded and state the resulting recurrence and complexity.

In the divide and conquer closest pair of points algorithm, the strip step compares each point only with a constant number of following points in the y-sorted strip. Prove that constant is bounded and state the resulting recurrence and complexity.

Approach: Every point in the strip lies within delta of the dividing line. Tile the region ahead of a given point with squares of side delta/2 and count how many points can fit.

O(n log n). In the closest pair algorithm, let delta be the smaller of the two half-solutions. Only points within delta of the dividing line can improve on it, and for a point p in that strip any improving partner must lie in the delta by 2 delta rectangle ahead of p in y. The packing bound comes from dividing that rectangle into squares of side delta/2, which gives 8 squares, and no square can hold two points, because two points inside one square are within delta * sqrt(2) / 2 which is less than delta, contradicting that each half already has minimum separation delta. So at most 8 points sit in the rectangle including p itself, and comparing each point with the next 7 in y order suffices. Keeping the points y-sorted by merging the two sorted halves makes the combine step O(n), so the recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). Sorting by y inside each call instead would give T(n) = 2T(n/2) + O(n log n) = O(n log^2 n), which is the usual implementation mistake.

Follow-up: What is the expected complexity of the randomised grid based closest pair algorithm and what does it assume?

Key concepts: closest pair, strip argument, packing bound, recurrence.