Selecting distances in the plane
Publication
, Journal Article
Agarwal, PK; Aronov, B; Sharir, M; Suri, S
Published in: Algorithmica
May 1, 1993
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 best-known 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 Springer-Verlag New York Inc.
Published In
Algorithmica
DOI
EISSN
1432-0541
ISSN
0178-4617
Publication Date
May 1, 1993
Volume
9
Issue
5
Start / End Page
495 / 514
Related Subject Headings
- Computation Theory & Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Agarwal, P. K., Aronov, B., Sharir, M., & Suri, S. (1993). Selecting distances in the plane. Algorithmica, 9(5), 495–514. https://doi.org/10.1007/BF01187037
Agarwal, P. K., B. Aronov, M. Sharir, and S. Suri. “Selecting distances in the plane.” Algorithmica 9, no. 5 (May 1, 1993): 495–514. https://doi.org/10.1007/BF01187037.
Agarwal PK, Aronov B, Sharir M, Suri S. Selecting distances in the plane. Algorithmica. 1993 May 1;9(5):495–514.
Agarwal, P. K., et al. “Selecting distances in the plane.” Algorithmica, vol. 9, no. 5, May 1993, pp. 495–514. Scopus, doi:10.1007/BF01187037.
Agarwal PK, Aronov B, Sharir M, Suri S. Selecting distances in the plane. Algorithmica. 1993 May 1;9(5):495–514.
Published In
Algorithmica
DOI
EISSN
1432-0541
ISSN
0178-4617
Publication Date
May 1, 1993
Volume
9
Issue
5
Start / End Page
495 / 514
Related Subject Headings
- Computation Theory & Mathematics