On the maximum number of tangencies among $1$-intersecting curves
This work addresses a combinatorial geometry conjecture by Pach, offering incremental improvements in theoretical bounds for arc tangencies.
The paper tackles the problem of bounding the maximum number of tangencies among families of Jordan arcs with specific intersection properties, improving the best known upper bounds from O(n^{7/4}) to O(n^{5/3}) for arcs with at most one common point and to O(n^{3/2}) for arcs with exactly one common point, and also provides new bounds for monotone arcs.
According to a conjecture of Pach, there are $O(n)$ tangent pairs among any family of $n$ Jordan arcs in which every pair of arcs has precisely one common point and no three arcs share a common point. This conjecture was proved for two special cases, however, for the general case the currently best upper bound is only $O(n^{7/4})$. This is also the best known bound on the number of tangencies in the relaxed case where every pair of arcs has \emph{at most} one common point. We improve the bounds for the latter and former cases to $O(n^{5/3})$ and $O(n^{3/2})$, respectively. We also consider a few other variants of these questions, for example, we show that if the arcs are \emph{$x$-monotone}, each pair intersects at most once and their left endpoints lie on a common vertical line, then the maximum number of tangencies is $Θ(n^{4/3})$. Without this last condition the number of tangencies is $O(n^{4/3}(\log n)^{1/3})$, improving a previous bound of Pach and Sharir. Along the way we prove a graph-theoretic theorem which extends a result of Erdős and Simonovits and may be of independent interest.