Selecting distances in the plane

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationProc Sixth Annu Symp Comput Geom
    PublisherPubl by ACM
    Pages321-331
    Number of pages11
    ISBN (Print)0897913620, 9780897913621
    DOIs
    StatePublished - 1990
    EventProceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA
    Duration: Jun 6 1990Jun 8 1990

    Publication series

    NameProc Sixth Annu Symp Comput Geom

    Conference

    ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
    CityBerkeley, CA, USA
    Period6/6/906/8/90

    ASJC Scopus subject areas

    • Engineering(all)

    Cite this

    Agarwal, P. K., Aronov, B., Sharir, M., & Suri, S. (1990). Selecting distances in the plane. In Proc Sixth Annu Symp Comput Geom (pp. 321-331). (Proc Sixth Annu Symp Comput Geom). Publ by ACM. https://doi.org/10.1145/98524.98597