Selecting distances in the plane

We present a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n^4/3 log^8/3n). The algorithm can also be made deterministic, using a more complicated technique, with only a slight increase in its running time. A much simpler deterministic version of our procedure runs in time O(n^3/2 log^5/2n). All versions improve the previously best-known upper bound of O(@#@ n^9/5 log^4/5n) by Chazelle [Ch]. A simple O(n log n)-time algorithm for computing an approximation of the median distance is also presented.