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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics