Efficient randomized incremental algorithm for the closest pair problem using Leafary trees

We present a new data structure, the Leafary tree, for designing an efficient randomized algorithm for the Closest Pair Problem. Using this data structure, we show that the Closest Pair of 22 points in D-dimensional space, where, D greater than or equal to 2, is a fixed constant, can be found in O(n log n/log log n) expected time. The algorithm does not employ hashing.