On Regular Vertices of the Union of Planar Convex Objects
Let C be a collection of n compact convex sets in the plane such that the boundaries of any pair of sets in C intersect in at most s points for some constant s >= 4. We show that the maximum number of regular vertices (intersection points of two boundaries that intersect twice) on the boundary of the union U of C is O*(n(4/3)), which improves earlier bounds due to Aronov et al. (Discrete Comput. Geom. 25, 203-220, 2001). The bound is nearly tight in the worst case. In this paper, a bound of the form O*(f(n)) means that the actual bound is C(epsilon)f (n) . n(epsilon) for any epsilon > 0, where C(epsilon) is a constant that depends on epsilon (and generally tends to infinity as epsilon decreases to 0).
regular vertices geometric arrangements union of planar regions lower envelopes bi-clique decompositions (1/r)-cuttings