A simple randomized O(n log n)–time closest-pair algorithm in doubling metrics

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.