# Closest Pair of Points Algorithm - Fortune and Hopcroft

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.

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