Selecting distances in the plane
Selecting distances in the plane
复制标题
选择平面中的距离
DOI：
10.1007/bf01187037
复制
发表时间：
1990
期刊：
影响因子：
1.1
通讯作者：
S. Suri
中科院分区：
文献类型：
--
作者：
P. Agarwal;B. Aronov;M. Sharir;S. Suri
We present a randomized algorithm for computing the kth smallest distance in a set ofn points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n4/3 log8/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(n3/2 log5/2n). All versions improve the previously best-known upper bound ofO(@#@ n9/5 log4/5n) by Chazelle [Ch]. A simpleO(n logn)-time algorithm for computing an approximation of the median distance is also presented.
