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:
- The step where subproblems are combined takes place in one lower dimension.
- 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 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.