Return to Answer

it seems that there is little known about the d-dimensional version

No, quite the opposite. Generalizing the divide-and-conquer algorithm from Wikipedia to the d dimensional case is so straight forward that the Wikipedia authors probably thought it would not be worth to explain any further details.

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 the argument why step 4 can be accomplished in linear time is still true for d dimensions. 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.

Wikipedia does not describe in detail how to implement this (not even for d=2), you will find the gory details here, which includes the case d>2. Note that the total running time for higher dimensions is O(n * log(n)^(d-1)), since for step 4 one has to sort for each coordinate (except x) individually.

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 for the planar case).

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

it seems that there is little known about the d-dimensional version

No, quite the opposite. Generalizing the divide-and-conquer algorithm from Wikipedia to the d dimensional case is so straight forward that the Wikipedia authors probably thought it would not be worth to explain any further details.

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 the argument why step 4 can be accomplished in linear time is still true for d dimensions. 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. Wikipedia does not describe in detail how to implement this (not even for d=2), but it is indeed possible to do this in linear time, see here.

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 for the planar case).

it seems that there is little known about the d-dimensional version

No, quite the opposite. Generalizing the divide-and-conquer algorithm from Wikipedia to the d dimensional case is so straight forward that the Wikipedia authors probably thought it would not be worth to explain any further details.

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 the argument why step 4 can be accomplished in linear time is still true for d dimensions. 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. 

Wikipedia does not describe in detail how to implement this (not even for d=2), you will find the gory details here, which includes the case d>2. Note that the total running time for higher dimensions is O(n * log(n)^(d-1)), since for step 4 one has to sort for each coordinate (except x) individually.

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 for the planar case).

it seems that there is little known about the d-dimensional version

No, quite the opposite. Generalizing the divide-and-conquer algorithm from Wikipedia to the d dimensional case is so straight forward that the Wikipedia authors probably thought it would not be worth to explain any further details.

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 the argument why step 4 can be accomplished in linear time is still true for d dimensions. 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.

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 for the planar case).

it seems that there is little known about the d-dimensional version

No, quite the opposite. Generalizing the divide-and-conquer algorithm from Wikipedia to the d dimensional case is so straight forward that the Wikipedia authors probably thought it would not be worth to explain any further details.

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 the argument why step 4 can be accomplished in linear time is still true for d dimensions. 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. Wikipedia does not describe in detail how to implement this (not even for d=2), but it is indeed possible to do this in linear time, see here.

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 for the planar case).