Incidences in Three Dimensions and Distinct Distances in the Plane

Source abstract

We first describe a reduction from the problem of lower-bounding the number of distinct distances determined by a set S of s points in the plane to an incidence problem between points and a certain class of helices (or parabolas) in three dimensions. We offer conjectures involving the new set-up, but are still unable to fully resolve them. Instead, we adapt the recent new algebraic analysis technique of Guth and Katz [9], as further developed by Elekes, Kaplan and Sharir [6], to obtain sharp bounds on the number of incidences between these helices or parabolas and points in ℝ 3 . Applying these bounds, we obtain, among several other results, the upper bound O ( s 3 ) on the number of rotations (rigid motions) which map (at least) three points of S to three other points of S . In fact, we show that the number of such rotations which map at least k ≥ 3 points of S to k other points of S is close to O ( s 3 / k 12/7 ). One of our unresolved conjectures is that this number is O ( s 3 / k 2 ), for k ≥ 2. If true, it would imply the lower bound Ω( s /log s ) on the number of distinct distances in the plane.