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.