Selecting distances in the plane

Pankaj K. Agarwal, Boris Aronov, Micha Sharir, Subhash Suri

    Research output: Contribution to journalArticle

    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 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.

    Original languageEnglish (US)
    Pages (from-to)495-514
    Number of pages20
    JournalAlgorithmica
    Volume9
    Issue number5
    DOIs
    StatePublished - May 1993

    Keywords

    • Arrangements
    • Parametric search
    • Random-sampling

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Selecting distances in the plane'. Together they form a unique fingerprint.

  • Cite this

    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