Probabilistic Analysis of a Closest Pair Algorithm

Abstract:

In this paper we give a probabilistic analysis of the recent algorithm due to Hinrichs, Nievergelt, and Schorn for solving the closest pair problem. The analysis that we present is made under the algebraic decision tree model of computation (not requiring the use of floor functions) which distinguishes it from the grid-method techniques of Bentley, Weide, and Yao. The result that we derive is that - given n points uniformly distributed in the unit square and then sorted - a simple linear sweep through the points determines the closest pair in O(n sqrtlog n) expected time. We close the paper by discussing the
possibility that it might be possible to dispense with the sqrtlog n factor completely; that is, the sweep algorithm might actually have a linear expected running time.