0
$\begingroup$

I am interested in implemented the deterministic ${O(n\log(\log(n)))}$ algorithm for the closest pair of points problem described here by Fortune and Hopcroft: https://ecommons.cornell.edu/bitstream/handle/1813/7460/78-340.pdf

In particular I would like to have a solution to the two-dimensional case.

They say: "The algorithm is based on the following observation: suppose we can find an interval size such that at most one point falls within each interval, and there are two nonempty adjacent intervals. Then to determine the closest pair we need only examine, for each point, the intervals surrounding the point". And for the one dimensional case which they describe in detail, the initial interval size is selected by taking (max(S) - min(S))/n where ${S}$ is the collection of points and ${n}$ is the number of points.

They claim the extension to higher dimensions is "obvious", but it's not at all clear to me how this above line might be generalised.

Does anyone have any suggestions? Many thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

One thing that you might not be aware of is that there's a 'hidden' exponential factor (it's explained on page 3). In $k$ dimensions the runtime is $O(kn \log(\log(n)) + 3^kn)$, as when you partition $k$-dimensional space into hypercubes each cube has $3^k - 1$ neighbors.

The rest of the algorithm really is 'obvious' then: you split your space up in hypercubes (which is just a fancy word for splitting up each dimension separately into intervals). Each point will then map to exactly one cube, and the rest of the algorithm follows.

E.g. suppose our interval size is $1$ and our domain is $[0, 10)$. Then in 1D we have that the point $3.4$ maps to bucket $3$ and $8.8$ maps to bucket $8$. In three dimensions if our interval size and (per-dimension) domain is the same, we have that $(2.3, 8.4, 4.4)$ maps to bucket $(2, 8, 4)$ and $(4.1, 5.2, 9.5)$ maps to $(4, 5, 9)$. So you end up with three-dimensional buckets but the algorithm hashes the buckets afterwards so that doesn't matter.

If you have anything more than two or three dimensions my suggestion would be to look for another algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Splitting each dimension into intervals is fine, but my question is how? There's no reason that max(S) - min(S)/n will be the same for each dimension, so if they are to be hypercubes and not hypercuboids then how do we decide which one to go for? I've tried taking the maximum but that doesn't seem quite right? $\endgroup$
    – M. McIlree
    Mar 12, 2021 at 11:41
  • $\begingroup$ @M.McIlree That is just a safe starting value. The maximum of that over all dimensions works, I believe. $\endgroup$
    – orlp
    Mar 12, 2021 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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