Selecting distances in the plane

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

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


    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
    Number of pages11
    ISBN (Print)0897913620, 9780897913621
    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


    ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
    CityBerkeley, CA, USA

    ASJC Scopus subject areas

    • General Engineering

    Cite this