Distinct distances in three and higher dimensions

Boris Aronov, János Pach, Micha Sharir, Gabor Tardos

    Research output: Contribution to journalArticlepeer-review


    Improving an old result of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl, we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n 77/141-ε) = Ω(n 0.546), for any Ε > 0. Moreover, there always exists a point p ∈ P from which there are at least so many distinct distances to the remaining elements of P. The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.

    Original languageEnglish (US)
    Pages (from-to)283-293
    Number of pages11
    JournalCombinatorics Probability and Computing
    Issue number3
    StatePublished - May 2004

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Statistics and Probability
    • Computational Theory and Mathematics
    • Applied Mathematics


    Dive into the research topics of 'Distinct distances in three and higher dimensions'. Together they form a unique fingerprint.

    Cite this