An efficient randomized algorithm for the closest pair problem on colored point sets
Veezhinathan Kamakoti, Kamala Krithivasan, Chandrasekharan Pandu Rangan · Nordic journal of computing · 1995
We present a simple randomized algorithm for finding the Closest Foreign Pair, in a set of n points in D-dimensional space, where D ≥ 2 is a fixed constant and the distances are measured in the L1 and the L∞ metric. The algorithm runs in O(nlogD-1 n/log log n) time with high probability for the L∞ metric and in O(n log2D-1-1 n/log log n) time with high probability for the L1 metric.