On the number of touching pairs in a set of planar curves (Q1693324): Difference between revisions

The authors deal with the problem of finding the upper bound on the number of touchings in a given set of pseudo-segments, i.e., set of Jordan arcs in which each pair of curves meets (crosses or touches) at most once. Using a planar graph drawing that corresponds to the set of \(n\) pseudo-segments (vertices are the crossings and touchings, the edges are the sections of the curves between neighbouring intersections) the authors prove that the number of touchings between the curves is \(O(t^2 n)\), where \(t\) is the number of faces that contain an endpoint of at least one curve from the set. Moreover, they show that the upper bound of touchings for a set of double-grounded and grounded pseudo-segments is \(O(n)\) and \(O(t n)\), respectively.