Eliminating cycles, cutting lenses, and bounding incidences

The talk covers two unrelated topics in combinatorial geometry that have recently reached a confluence: incidences between points and curves in the plane, or surfaces in higher dimensions, and elimination of cycles in the depth relation of lines in 3-space. Recent progress on the latter problem, inspired by the new algebraic machinery of Guth and Katz, has yielded a nearly tight bound, of roughly $n^{3/2}$, on the number of cuts needed to eliminate all cycles for a set of n lines, or simply-shaped algebraic curves, in 3-space. This in turn leads to a similar bound on the number of cuts that are needed to turn a collection of n constant-degree algebraic arcs in the plane into a collection of pseudo-segments (i.e., each pair of the new subarcs intersect at most once). This leads, among several other applications, to improved incidence bounds between points and algebraic arcs in the plane, which are better than the older general bound of Pach and Sharir, for any number of “degrees of freedom” of the curves. It also leads to several new bounds for incidences between points and planes or points and spheres in three dimensions.

Based on joint works with Boris Aronov, Noam Solomon, and Joshua Zahl.