Selecting distances in the plane
Published
Journal Article
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.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Aronov, B; Sharir, M; Suri, S
Published Date
- May 1, 1993
Published In
Volume / Issue
- 9 / 5
Start / End Page
- 495 - 514
Electronic International Standard Serial Number (EISSN)
- 1432-0541
International Standard Serial Number (ISSN)
- 0178-4617
Digital Object Identifier (DOI)
- 10.1007/BF01187037
Citation Source
- Scopus