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.