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.
Two key features of the divide and
conquer strategy are these:
The step where subproblems are
combined takes place in one lower
The subproblems in the combine step
satisfy a sparsity condition.
Sparsity Condition: Any cube with side
length 2δ contains O(1) points of S.
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
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.
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):
Sort points according to their x-coordinates.
Split the set of points into two equal-sized subsets by a (d-1) dimensional, vertical hyper-plane defined by x=xmid.
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.
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".
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).