2017/08/07 by Pach, János, Rubin, Natan, Tardos, Gábor
#05C10 #05C35 #05D99 #52C10 #52C30 #52C45 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.1708.02077
If two Jordan curves in the plane have precisely one point in common, and there they do not properly cross, then the common point is called a \em touching point. The main result of this paper is a Crossing Lemma for simple curves: Let X and T stand for the sets of intersection points and touching points, respectively, in a family of n simple curves in the plane, no three of which pass through the same point. If |T|>cn, for some fixed constant c>0, then we prove that |X|=Ω(|T|(loglog(|T|/n))1/504). In particular, if |T|/n→∞, then the number of intersection points is much larger than the number of touching points. As a corollary, we confirm the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between n pairwise intersecting simple closed (i.e., Jordan) curves in the plane, no three of which pass through the same point, is at least (1-o(1))n2.