On Rich Points and Incidences with Restricted Sets of Lines in 3-Space
Micha Sharir, Noam Solomon · Journal of Computational Geometry (Carleton University) · 2020
Let $L$ be a set of $n$ lines in $\mathbb{R}^3$ that is contained, when represented as points in the four-dimensional Plücker space of lines in $\mathbb{R}^3$, in an irreducible variety $T$ of constant degree which is non-degenerate with respect to $L$ (see below). We show: (1) If $T$ is two-dimensional, the number of $r$-rich points (points incident to at least $r$ lines of $L$) is $O(n^{4/3+\varepsilon}/r^2)$, for $r \ge 3$ and for any $\varepsilon > 0$, and, if at most $n^{1/3}$ lines of $L$ lie on any common regulus, there are at most $O(n^{4/3+\varepsilon})$ $2$-rich points. For $r$ larger than some sufficiently large constant, the number of $r$-rich points is also $O(n/r)$. As an application, we deduce (with an $\varepsilon$-loss in the exponent) the bound obtained by Pach and de Zeeuw (2017) on the number of distinct distances determined by $n$ points on an irreducible algebraic curve of constant degree in the plane that is not a line nor a circle. (2) If $T$ is two-dimensional, the number of incidences between $L$ and a set of $m$ points in $\mathbb{R}^3$ is $O(m + n)$. (3) If $T$ is three-dimensional and nonlinear, the number of incidences between $L$ and a set of $m$ points in $\mathbb{R}^3$ is $O(m^{3/5}n^{3/5} + (m^{11/15}n^{2/5} + m^{1/3}n{2/3})s^{1/3} + m + n)$, provided that no plane contains more than $s$ of the points. When $s = O(\min \{ n{3/5}/m^{2/5}, m^{1/2} \})$, the bound becomes $O(m^{3/5}n^{3/5} + m + n)$. As an application, we prove that the number of incidences between $m$ points and $n$ lines in $\mathbb{R}^4$ contained in a quadratic hypersurface (which does not contain a hyperplane) is $O(m^{3/5}n^{3/5} + m + n)$. The proofs use, in addition to various tools from algebraic geometry, recent bounds on the number of incidences between points and algebraic curves in the plane.