Unit Distances in Three Dimensions

Abstract

We show that the number of unit distances determined by n points in ℝ 3 is O ( n 3/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].

Locations

• reroDoc Digital Library - View - PDF
• arXiv (Cornell University) - View - PDF
• CiteSeer X (The Pennsylvania State University) - View - PDF
• Repository for Publications and Research Data (ETH Zurich) - View - PDF
• Combinatorics Probability Computing - View