A note on distinct distances
Orit E. Raz · Combinatorics Probability Computing · 2020
Abstract We show that, for a constant-degree algebraic curve γ in ℝ D , every set of n points on γ spans at least Ω( n 4/3 ) distinct distances, unless γ is an algebraic helix , in the sense of Charalambides [2]. This improves the earlier bound Ω( n 5/4 ) of Charalambides [2]. We also show that, for every set P of n points that lie on a d -dimensional constant-degree algebraic variety V in ℝ D , there exists a subset S ⊂ P of size at least Ω( n 4/(9+12( d −1)) ), such that S spans $\left({\begin{array}{*{20}{c}} {|S|} \\ 2 \\\end{array}} \right)$ distinct distances. This improves the earlier bound of Ω( n 1/(3 d ) ) of Conlon, Fox, Gasarch, Harris, Ulrich and Zbarsky [4]. Both results are consequences of a common technical tool.