On regular vertices of the union of planar convex objects (Q1017923): Difference between revisions

Let \(\mathcal{C}\) be a collection of \(n\) compact convex sets in the plane such that the boundaries of any pair of sets in \(\mathcal{C}\) intersect in at most \(s\) points for some constant \(s\geq 4\). Let \(U\) denote the union of \(\mathcal{C}\). If the boundaries of a pair of sets in \(\mathcal{C}\) intersect exactly twice, their two intersection points are called regular. Several recent papers have considered the problem of obtaining bounds on the number of regular intersection points that can appear on the boundary of \(U\). The authors show that for each \(\varepsilon>0\) there is a constant \(C_\varepsilon\) such that the maximum number of regular intersection points of \(\mathcal{C}\) which belong to the boundary of \(U\) is \(\leq C_\varepsilon n^{\frac43+\varepsilon}\). This result improves earlier bounds from \textit{B. Aronov, A. Efrat, D. Halperin} and \textit{M. Sharir} [Discrete Comput. Geom. 25, No.~2, 203--220 (2001; Zbl 0996.68215)]. The bound is nearly tight in the worst case.