Distinct distances in three and higher dimensions

Boris Aronov, János Pach, Micha Sharir, Gábor Tardos

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


    Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n77/141-ε) = Ω(n0.546), for any ε > 0. Moreover, there always exists a point p ∈ P from which there are at least these 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)
    Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
    Number of pages6
    StatePublished - 2003
    Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
    Duration: Jun 9 2003Jun 11 2003


    Other35th Annual ACM Symposium on Theory of Computing
    Country/TerritoryUnited States
    CitySan Diego, CA


    • Distinct distances
    • Incidences
    • Point configurations

    ASJC Scopus subject areas

    • Software

    Cite this