Consider a metric space (P, dist) with N points whose doubling dimension is a constant. We present a simple, randomized, and recursive algorithm that computes, in O(N log N) expected time, the closest-pair distance in P. To generate recursive calls, we use previous results of Har-Peled and Mendel, and Abam and Har-Peled for computing a sparse annulus that separates the points in a balanced way.
