Selecting distances in the plane

Journal Article

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. The expected running time of our algorithm is O(n4/3 log8/3 n). A deterministic version of our procedure runs in time O(n3/2 log5/2 n). Both versions improve the previously best known upper bound of O(n9/5 log4/5 n) by Chazelle. A simple O(n log n) time algorithm for computing an approximation of the median distance is also presented.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B; Sharir, M; Suri, S

Published Date

  • January 1, 1990

Start / End Page

  • 321 - 331

Digital Object Identifier (DOI)

  • 10.1145/98524.98597

Citation Source

  • Scopus