How to generalize the planar case of the closest pair problem to d dimensions?

Question

I'm trying to create a solution for the Closest pair problem using d-dimensional points. I've done a thorough search on google but it seems that there is no explanation for the d-dimensional case apart from what is on wikipedia:

the divide-and-conquer algorithm can be generalized to take O(n log n) time for any constant value of d.

and this document I found stating:

• Two key features of the divide and conquer strategy are these:
  1. The step where subproblems are combined takes place in one lower dimension.
  2. The subproblems in the combine step satisfy a sparsity condition.
  3. Sparsity Condition: Any cube with side length 2δ contains O(1) points of S.
  4. Note that the original problem does not necessarily have this condition.

...

• Given n points with δ-sparsity condition, find all pairs within distance ≤ δ.
• Divide the set into S1, S2 by a median place H. Recursively solve the problem in two halves.
• Project all points lying within δ thick slab around H onto H. Call this set S'
• Recursively solve the problem for S' in d − 1 space.

but I can't wrap my head around the directions given in the documents above. Can someone describe in layman's terms how do I generalize the 2d solution to d dimensions? Is it even necessary or the 2d solution will work?

Understanding the 2d case was not so hard but it seems that there is little known about the d-dimensional version and I'm no mathematician.

Answer 1

Generalizing the divide-and-conquer algorithm from Wikipedia to the d dimensional case is straight forward:

Here is the adopted algorithm description (changes in bold):

1. Sort points according to their x-coordinates.

2. Split the set of points into two equal-sized subsets by a (d-1) dimensional, vertical hyper-plane defined by x=xmid.

3. Solve the problem recursively in the "left" and "right" half of the coordinate space, defined by x<=xmid and x>=xmid . This yields the left-side and right-side minimum distances dLmin and dRmin, respectively.

4. Find the minimal distance dLRmin among the set of pairs of points in which one point lies on the "left" of the dividing hyper-plane and the second point lies to the "right".

5. The final answer is the minimum among dLmin, dRmin, and dLRmin.

Note that step 4 can be accomplished in linear time for 2 dimensions, but needs O(n * log(n)^(d-1)) steps for d dimensions. More details are described here, which includes the case d>2.

Note further that for real world data it may be a good idea to switch between different coordinate axes from one recursive step to the next (but that applies already to the planar case).