Improved bounds for incidences between points and circles

Abstract

We establish an improved upper bound for the number of incidences between m points and n circles in three dimensions. The previous best known bound, originally established for the planar case and later extended to any dimension $\ge 2$, is $O\ast (m^{2/3}{n}^{2/3}+m^{6/11}{n}^{9/11}+m+n)$, where the $O\ast (\cdot )$ notation hides sub-polynomial factors. Since all the points and circles may lie on a common plane (or sphere), it is impossible to improve the bound in R^3 without first improving it in the plane. Nevertheless, we show that if the set of circles is required to be "truly three-dimensional" in the sense that no sphere or plane contains more than $q$ of the circles, for some $q<<n$, then the bound can be improved to \[O*(m^{3/7}n^{6/7} + m^{2/3}n^{1/2}q^{1/6} + m^{6/11}n^{15/22}q^{3/22} + m + n). \] For various ranges of parameters (e.g., when $m=\Theta (n)$ and $q=o(n^{7/9})$), this bound is smaller than the lower bound $\Omega \ast (m^{2/3}{n}^{2/3}+m+n)$, which holds in two dimensions. We present several extensions and applications of the new bound: (i) For the special case where all the circles have the same radius, we obtain the improved bound $O\ast (m^{5/11}{n}^{9/11}+m^{2/3}{n}^{1/2}{q}^{1/6}+m+n$. (ii) We present an improved analysis that removes the subpolynomial factors from the bound when $m=O(n^{3/2-\eps})$ for any fixed $\epsilon >0$. (iii) We use our results to obtain the improved bound $O(m^{15/7})$ for the number of mutually similar triangles determined by any set of $m$ points in R^3. Our result is obtained by applying the polynomial partitioning technique of Guth and Katz using a constant-degree partitioning polynomial (as was also recently used by Solymosi and Tao). We also rely on various additional tools from analytic, algebraic, and combinatorial geometry.

References in corpus (1)

• On the Erdos distinct distance problem in the plane

Cited by in corpus (11)

• Polynomial partitioning for a set of varieties
• A Szemeredi-Trotter type theorem in ${\mathbb{R}}^4$
• Breaking the 3/2 barrier for unit distances in three dimensions
• Incidences between points and lines in R^4
• Distinct and repeated distances on a surface and incidences between points and spheres
• Highly incidental patterns on a quadratic hypersurface in ${\mathbb{R}}^4$
• Shattered Sets and the Hilbert Function
• Multilevel polynomial partitions and simplified range searching
• Incidences with curves in R^d
• Incidence estimates for well spaced tubes
• Incidences with curves in three dimensions