Fast spatial decomposition and closest pair computation for limited precision input

In this paper we show that if the input points to the geometric closest pai r problem are given with limited precision (each coordinate is specified wi th O(log n) bits), then we can compute the closest pair in O (n log log n) time. We also apply our spatial decomposition technique to the k-nearest ne ighbor and n-body problems, achieving similar improvements. To make use of the limited precision of the input points, we use a reasonab le machine model that allows "bit shifting" in constant time-we believe tha t this model is realistic, and provides an interesting way of beating the O mega (n log n) lower bound that exists for this problem using the more typi cal algebraic RAM model.