Selecting distances in the plane

We describe 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 [Me1]. The expected running time of our algorithm is O(n4/3 log 8/3 n). A deterministic version of our procedure runs in time O(n3/2 log5/2 n). Both versions improve the previously best known upper bound of O(n9/5 log4/5 n) by Chazelle [Ch]. A simple O(n log n) time algorithm for computing an approximation of the median distance is also presented.