Unit Distances in Three Dimensions
Haim Y. Kaplan, Jiřı́ Matoušek, Zuzana Safernová, Micha Sharir · Combinatorics Probability Computing · 2012
We show that the number of unit distances determined bynpoints in ℝ3isO(n3/2), slightly improving the bound of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl [5], established in 1990. The new proof uses the recently introduced polynomial partitioning technique of Guth and Katz [12]. While this paper was still in a draft stage, a similar proof of our main result was posted to the arXiv by Joshua Zahl [28].