Incidences between points and polynomial graphs
= Incidences between points and polynomial graphs
For $m$ distinct real univariate polynomials of degree at most $d$ and $n$ points with distinct first coordinates, the number of incidences between the points and the polynomial graphs is
$$
O\left(m+n+d^{1/3}m^{2/3}n^{2/3}\right).
$$
Two polynomial graphs meet at most $d$ times, so the graph formed from consecutive incidences has $O(dm^2)$ crossings; the <Crossing lemma> supplies the lower bound.