Incidences with Curves in ℝ^d

Abstract

We prove that the number of incidences between m points and n bounded-degree curves with k degrees of freedom in R^d is O (m^((k/dk-d+1) + ε) n^(dk-d/dk-d+1) + ∑^(d-1)_(j=2) m^((k/jk-j+1) + ε) n^(d(j-1)(k-1)/(d-1)(jk-j+1)) q^((d-j)(k-1)/(d-1)(jk-j+1))_j + m + n), for any ε > 0, where the constant of proportionality depends on k, ε and d, provided that no j-dimensional surface of degree ⩽ c_(j) (k; d; ε), a constant parameter depending on k, d, j, and ε, 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 ℝ^d. It generalizes a recent result of Sharir and Solomon [21] concerning point-line incidences in four dimensions (where d = 4 and k = 2), and partly generalizes a recent result of Guth [9] (as well as the earlier bound of Guth and Katz [11]) 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 [8], in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi [5] and by Hablicsek and Scherr [13] concerning rich lines in high-dimensional spaces. Our bound is not known to be tight in most cases.

Files

Additional details