Incidences with Curves in $\mathbb{R}^d$

Micha Sharir, Adam Sheffer, Noam Solomon

Abstract


We prove that the number of incidences between $m$ points and $n$ bounded-degree curves with $k$ degrees of freedom in ${\mathbb R}^d$ is\[ O\left(m^{\frac{k}{dk-d+1}+\varepsilon}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\varepsilon}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n\right),\]for any $\varepsilon>0$, where the constant of proportionality depends on $k, \varepsilon$ and $d$, provided that no $j$-dimensional surface of degree $\le c_j(k,d,\varepsilon)$, a constant parameter depending on $k$, $d$, $j$, and $\varepsilon$, contains more than $q_j$ input curves, and that the $q_j$'s satisfy certain mild conditions. 

This bound generalizes the well-known planar incidence bound of Pach and Sharir to $\mathbb{R}^d$. It generalizes a recent result of Sharir and Solomon concerning point-line incidences in four dimensions (where d=4 and k=2), and partly generalizes a recent result of Guth (as well as the earlier bound of Guth and Katz) in three dimensions (Guth's three-dimensional bound has a better dependency on $q_2$). It also improves a recent d-dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl, in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi and by Hablicsek and Scherr concerning rich lines in high-dimensional spaces. Our bound is not known to be tight in most cases.


Keywords


Geometic incidences; Discrete geometry; Polynomial partitioning; Polynomial curves

Full Text: PDF