Math @ Duke

Publications [#235575] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M; Suri, S, Selecting distances in the plane,
Algorithmica, vol. 9 no. 5
(1993),
pp. 495514, ISSN 01784617 [doi]
(last updated on 2018/05/20)
Abstract: 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(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 bestknown upper bound of O(@#@ n9/5 log4/5n) by Chazelle [Ch]. A simple O(n log n)time algorithm for computing an approximation of the median distance is also presented. © 1993 SpringerVerlag New York Inc.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

