Incidences between points on a variety and planes in R^3

Abstract

In this paper we establish an improved bound for the number of incidences between a set $P$ of $m$ points and a set $H$ of $n$ planes in ${\mathbb{R}}^3$, provided that the points lie on a two-dimensional nonlinear irreducible algebraic variety $V$ of constant degree. Specifically, the bound is $$O\left(m^{2/3}{n}^{2/3}+m^{6/11}{n}^{9/11}{\log }^{\beta }(m^3/n)+m+n+\sum _{\ell }|P_{\ell }|\cdot |H_{\ell }|\right),$$ where the constant of proportionality and the constant exponent $\beta$ depend on the degree of $V$, and where the sum ranges over all lines $\ell$ that are fully contained in $V$ and contain at least one point of $P$, so that, for each such $\ell$, $P_{\ell }=P\cap \ell$ and $H_{\ell }$ is the set of the planes of H that contain $\ell$. In addition, ${\sum }_{\ell }|P_{\ell }|=O(m)$ and ${\sum }_{\ell }|H_{\ell }|=O(n)$. This improves, for this special case, the earlier more general bound of Apfelbaum and Sharir (see also Brass and Knauer as well as Elekes and Tóth). This is a generalization of the incidence bound for points and circles in the plane (cf. Aronov et al., Aronov and Sharir, Marcus and Tardos), and is based on a recent result of Sharir and Zahl on the number of cuts that turn a collection of algebraic curves into pseudo-segments. The case where $V$ is a quadric is simpler to analyze, does not require the result of Sharir and Zahl, and yields the same bound as above, with $\beta =2/11$. We present an interesting application of our results to a problem, studied by Rudnev, on obtaining a lower bound on the number of distinct cross-ratios determined by $n$ real points, where our bound leads to a slight improvement in Rudnev's bound.

References in corpus (2)

• On the Erdos distinct distance problem in the plane
• Cutting Algebraic Curves into Pseudo-segments and Applications

Cited by in corpus (3)

• On distinct cross-ratios and related growth problems
• Two theorems on point-flat incidences
• Representation Complexity of Semi-algebraic Graphs