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

    Abstract

    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
    Pages541-546
    Number of pages6
    StatePublished - 2003
    Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
    Duration: Jun 9 2003Jun 11 2003

    Other

    Other35th Annual ACM Symposium on Theory of Computing
    CountryUnited States
    CitySan Diego, CA
    Period6/9/036/11/03

    Keywords

    • Distinct distances
    • Incidences
    • Point configurations

    ASJC Scopus subject areas

    • Software

    Cite this

    Aronov, B., Pach, J., Sharir, M., & Tardos, G. (2003). Distinct distances in three and higher dimensions. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 541-546)