Arrangements of arcs and pseudocircles (Q2365260)

The authors study a variant of a classical unsolved problem in computational geometry, and obtain complete results. Consider an arrangement \(A\) of \(n\) pseudo-circles in the plane, in which no three intersect in a point. Each intersection point \(v\) is contained in the interior of a certain number \(w(v)\) of the circles of \(A\). The classical problem is to find sharp upper bounds for the number of vertices \(v\) whose weight \(w(v)\) does not exceed \(k\). In this paper the authors derive sharp upper bounds for the number of vertices \(v_{\geq k}\) of weight \textit{at least} \(k\), and construct, for each \(n\), a single extremal arrangement \(A\) for which the upper bounds are attained simultaneously for all \(k\). An arrangement of pseudo-circles induces on each of its elements an arrangement of arcs, whose endpoints are the vertices of the arrangement. The weights of these vertices in the arrangement \(A\) can be read off as weights of vertices in the induced arrangement of arcs. Thus the authors study the possible weights of vertices and edges in an arrangement of arcs in a circle. They obtain complete characterizations of the integer sequences which may arise as weight sequences for edges or vertices in such an arrangement. Using these results the upper bound for the number of vertices of \(A\) of weight at least \(k\) is obtained, namely, \[ v_{\geq k}\leq (n+k)(n-k-1). \]