SELECTING DISTANCES IN THE PLANE

We present a randomized algorithm for computing the kth smallest dista nce 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 log8/3 n). The algorithm can also be made deterministic, us ing a more complicated technique, with only a slight increase in its r unning time. A much simpler deterministic version of our procedure run s in time O(n3/2 log5/2 n). All versions improve the previously best-k nown upper bound of O(n9/5 log4/5 n) by Chazelle [Ch]. A simple O(n lo g n)-time algorithm for computing an approximation of the median dista nce is also presented.