On the number of regular vertices of the union of jordan regions

Let C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. If the boundaries of two sets in C cross exactly twice, then their intersection points are called regular vertices of the arrangement A(C) . Let R(C) denote the set of regular vertices on the boundary of the union of C . We present several bounds on |R(C)| , depending on the type of the sets of C . (i) If each set of C is convex, then |R(C)|=O(n ^1.5+eps ) for any eps>0 . (ii) If no further assumptions are made on the sets of C , then we show that there is a positive integer r that depends only on s such that |R(C)|=O(n ^2-1/r ) . (iii) If C consists of two collections C ₁ and C ₂ where C ₁ is a collection of m convex pseudo-disks in the plane (closed Jordan regions with the property that the boundaries of any two of them intersect at most twice), and C ₂ is a collection of polygons with a total of n sides, then |R(C)|=O(m ^2/3 n ^2/3 +m +n) , and this bound is tight in the worst case. Received December 4, 1998, and in revised form June 3, 2000. Online publication Feburary 1, 2001.