An O(n log n log log n) Algorithm for the On-line Closest Pair Problem
Christian J. Schwarz, Michiel Smid · Symposium on Discrete Algorithms · 1992
Let V be a set of n points in k-dimensional space. It is shown how the closest pair in V can be maintained under insertions in O(log n log log n) amortized time, using O(n) amortized time, using O(n) space. Distances are measured in the Lt-metric, where 1 ≤ ∞. This gives an O(n log n log log n0 time on-line algorithm or computing the closest pair. The algorithm is based on Bentley's logarithmic method for decomposable searching problems. It uses a non-trivial extension of fractional cascading to k-dimensional space.