Selecting distances in the plane
Pankaj K. Agarwal, Boris S. Aronov, Micha Sharir, Subhash Suri · 1990
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 Ο(n4/3 log 8/3 n). A deterministic version of our procedure runs in time Ο(n3/2 log5/2 n). Both versions improve the previously best known upper bound of Ο(n9/5 log4/5 n) by Chazelle [Ch]. A simple Ο(n log n) time algorithm for computing an approximation of the median distance is also presented.