4

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.

3

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).

  • So what you are trying to say is that basically I only need to change this part: "One simply has to replace 6 * n distance calculations by c * n distance calculations, where c is the maximum number of points which fit into a d-dimensional box of size (dist, 2*dist, 2*dist, ..., 2*dist), when the shortest distance between the points is dist at minimum."? – Adam Arold Dec 29 '15 at 22:36
  • @AdamArold: that sentence is no algorithm, it is part of the proof that the running time is O(n * log(n)). – Doc Brown Dec 29 '15 at 23:29
  • I see. I know that I have to do c * n operations but when I implement it I have to know how many points should I scan for each p point within the δ distance of the median l line in d dimensions. I know that it is 6 for 2 dimensions but how do I know how much c is for d dimensions? – Adam Arold Dec 30 '15 at 2:14
  • @AdamArold: you do not have to know explicitly how big c is to implement the algorithm, the argument just shows that when you scan for the neighbors of p, you will never find more than c*n points. Moreover, I think I was wrong, step 4 needs more than linear time for d>2, see my edit. – Doc Brown Dec 30 '15 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.