Combinatorics, Probability and Computing



Paper

Distinct Distances in Three and Higher Dimensions


BORIS ARONOV a1 1 5 , JÁNOS PACH a2 2 5 , MICHA SHARIR a3 3 5 and GÁBOR TARDOS a4 4
a1 Department of Computer and Information Science, Polytechnic University, Brooklyn, NY 11201-3840, USA (e-mail: aronov@cis.poly.edu)
a2 City College, CUNY and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA (e-mail: pach@cims.nyu.edu)
a3 School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel, and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA (e-mail: michas@post.tau.ac.il)
a4 Rényi Institute, Hungarian Academy of Sciences, Pf. 127, H-1354 Budapest, Hungary (e-mail: tardos@renyi.hu)

Article author query
aronov b   [Google Scholar] 
pach j   [Google Scholar] 
sharir m   [Google Scholar] 
tardos g   [Google Scholar] 
 

Abstract

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 $\Omega(n^{77/141-\varepsilon})=\Omega(n^{0.546})$, for any $\varepsilon>0$. Moreover, there always exists a point $p\in 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.

(Published Online April 28 2004)
(Received June 2 2003)
(Revised September 3 2003)



Footnotes

1 Supported by NSF grants CCR-99-72568 and ITR CCR-00-81964.

5 Work on this paper was also supported by a grant from the US–Israeli Binational Science Foundation.

2 Supported by NSF grants CCR-97-32101 and CCR-00-98246, and by a PSC-CUNY Award.

3 Supported by NSF grants CCR-97-32101 and CCR-00-98246, by a grant from the Israel Science Fund (for a Center of Excellence in Geometric Computing), and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Part of the work on this paper was carried out when Micha Sharir visited ETH Zürich in the spring of 2001.

4 Supported by Hungarian Science Foundation grants OTKA T029255, OTKA T030059, and AKP 2000-78 2.1.