Multicolor Combination Lemma

We present an extension of the Combination Lemma of Guibas et al. (1983) th at expresses the complexity of one or several faces in the overlay of many arrangements (as opposed to just two arrangements in (Guibas et al. 1989)), as a function of the number of arrangements, the number of faces, and the complexities of these faces in the separate arrangements. Several applicati ons of the new Combination Lemma are presented. We first show that the comp lexity of a single face in an arrangement of k simple polygons with a total of n sides is Theta (n alpha(k)), where alpha(.) is the inverse of Ackerma nn's function. We also give a new and simpler proof of the bound O(root m l ambda(s+2)(n)) on the total number of edges of m faces in an arrangement of n Jordan arcs, each pair of which intersect in at most s points, where lam bda(s) (n) is the maximum length of a Davenport-Schinzel sequence of order s with n symbols. We extend this result, showing that the total number of e dges of m faces in a sparse arrangement of n Jordan arcs is O((il + root m root w)lambda(s+2)(n)/n), where w is the total complexity of the arrangemen t. Several other related results are also obtained. (C) 1999 Elsevier Scien ce B.V. All rights reserved.