Breaking the 3/2 barrier for unit distances in three dimensions

Abstract

We prove that every set of $n$ points in ${\mathbb{R}}^3$ spans $O(n^{295/197+\epsilon })$ unit distances. This is an improvement over the previous bound of $O(n^{3/2})$. A key ingredient in the proof is a new result for cutting circles in ${\mathbb{R}}^3$ into pseudo-segments.

44 pages, 0 figures. v3: This version fixes an error in the proof of Lemma 3.2 that was pointed out by Micha Sharir. The rest of the paper remains unchanged

References in corpus (1)

• Cutting Algebraic Curves into Pseudo-segments and Applications

Cited by in corpus (2)

• Sphere tangencies, line incidences, and Lie's line-sphere correspondence
• Nondegenerate spheres in four dimensions